grid47 Exploring patterns and algorithms
Sep 10, 2024
6 min read
Solution to LeetCode 572: Subtree of Another Tree Problem
Given the roots of two binary trees, root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree consists of a node in the tree and all of this node’s descendants.
Problem
Approach
Steps
Complexity
Input: The input consists of two binary trees, represented by their root nodes.
Defines the function `isSubtree` which checks if `subRoot` is a subtree of `root`. It returns `true` if `subRoot` is a subtree, otherwise `false`.
2 : Base Case - Null Root
if(!root) returnfalse;
Checks if the root of the tree is `null`. If it is, the function returns `false` because an empty tree can't contain any subtree.
3 : Check for Match
if(match(root, subRoot)) returntrue;
Calls the `match` function to check if the current node of `root` and `subRoot` match. If they do, the function returns `true`, indicating `subRoot` is a subtree starting at the current node.
4 : Recursion - Check Left Subtree
return isSubtree(root->left, subRoot) ||
Recursively checks if `subRoot` is a subtree of the left child of `root`. If the left subtree contains `subRoot`, the function will return `true`.
5 : Recursion - Check Right Subtree
isSubtree(root->right, subRoot);
Recursively checks if `subRoot` is a subtree of the right child of `root`. If the right subtree contains `subRoot`, the function will return `true`.
6 : Function Definition
boolmatch(TreeNode* r1, TreeNode* r2) {
Defines the helper function `match`, which checks if two binary trees `r1` and `r2` are identical.
7 : Base Case - Both Null
if(!r1 &&!r2) returntrue;
Checks if both nodes `r1` and `r2` are `null`. If both are `null`, the trees are considered identical (both empty).
8 : Base Case - One Null
if(!r1 ||!r2) returnfalse;
Checks if only one of the nodes is `null`. If one node is `null` and the other is not, the trees are not identical.
9 : Node Value Comparison
if(r1->val != r2->val) returnfalse;
Compares the values of the current nodes `r1` and `r2`. If the values are different, the trees are not identical.
10 : Recursive Check for Left and Right Subtrees
return match(r1->left, r2->left) &&
Recursively checks if the left children of `r1` and `r2` are identical. The function returns `true` if both left subtrees are identical.
11 : Recursive Check for Right Subtrees
match(r1->right, r2->right);
Recursively checks if the right children of `r1` and `r2` are identical. The function returns `true` if both right subtrees are identical.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n * m)
Description: In the worst case, we check every node in root, and for each node, we compare subRoot, resulting in a time complexity of O(n * m), where n is the number of nodes in root and m is the number of nodes in subRoot.
Best Case: O(1)
Worst Case: O(h)
Description: The space complexity is O(h) due to the recursion stack, where h is the height of the tree.
