572. Subtree of Another Tree — LeetCode(Python)
I got you!
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 tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
Example 1:
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: trueExample 2:
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: falseConstraints:
- The number of nodes in the
roottree is in the range[1, 2000]. - The number of nodes in the
subRoottree is in the range[1, 1000]. -104 <= root.val <= 104-104 <= subRoot.val <= 104
Solution:
identical() helper function —
Consider reading my solution for 100. Same Tree — LeetCode(Python) to better understand the code above.
We need a helper function to judge if the two subtrees we are considering are in-fact identical.
1. Iterative Approach (BFS) —
Explanation —
We can use a breadth-first search (BFS) traversal algorithm to iteratively solve the problem.
A queue is used to store all nodes in the tree level by level.
At every step, we pop / dequeue an element from the queue. If this node has a value equal to that of the subTree’s root, we check if both the subtrees are identical or not. True is returned if they are.
The, we append the left and right children of the current node into our stack.
The while loop terminates when the queue is empty, which means all nodes in the tree have been traversed and popped out from the queue.
So, now it is safe to say that no such subtree was found in our given tree. Therefore, we return False.
Time and Space Complexity —
We are visiting each node in the tree only a constant number of times in our BFS code, but we are calling identical() at every valid node, so we can say that our algorithm requires quadratic amount of time to run in the worst case.
Also, our queue will be storing a maximum of (n / 2) nodes when it reaches the final level. So, we assume the space complexity to be linear in the worst case, per tree — therefore, quadratic.
Thus, if m and n are the number of nodes in the given binary trees,
Time Complexity: O(mn)
Space Complexity: O(mn)
2. Recursive Approach (DFS) —
Explanation —
We could also use a depth-first search (DFS) traversal algorithm to solve this problem recursively.
We simply return True if the subTree is empty, because then our tree will have a copy of it. [this clause can be omitted because we are given that the subTree will have a positive number of nodes]
The base case of our recursion would be when we reach a leaf node in our tree, which is when we return False.
Else, we check if the current node in the tree is where our subTree is rooted at. If yes, we return True.
Otherwise we return the value of the recursive search on the left and right children of the current node.
Time and Space Complexity —
We are visiting each node in the tree only a constant number of times in our BFS code, but we are calling identical() at every valid node, so we can say that our algorithm requires quadratic amount of time to run in the worst case.
Also, the recursion stack could be storing all nodes in the tree in case of a really skewed tree (like a linked list). So, we assume the space complexity to be linear in the worst case, per tree — therefore, quadratic.
Thus, if m and n are the number of nodes in the given binary trees,
Time Complexity: O(mn)
Space Complexity: O(mn)
