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: true
Example 2:
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] Output: false
Constraints:
root tree is in the range [1, 2000].subRoot tree is in the range [1, 1000].-104 <= root.val <= 104-104 <= subRoot.val <= 104This approach involves using a recursive function to traverse the root tree and checking for a matching subtree starting from every node. A helper function can be used to check if trees rooted at specific nodes are identical.
The function isIdentical compares two trees recursively to check if they are identical. The main function isSubtree checks the root node against the subRoot using isIdentical and then calls itself recursively on the left and right children of the root node.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N*M), where N is the number of nodes in the root tree and M is the number of nodes in subRoot tree.
Space Complexity: O(min(N, M)), depending on the tree height during recursion.
Another approach to solving this problem is by converting the trees into their preorder traversal strings with marker symbols for nulls, and then checking if the subRoot string is a substring of the root string.
This approach serializes both trees using a preorder traversal which handles null nodes explicitly. The serialized string of subRoot is then checked as a substring within that of root.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N + M + N*M), where N and M are the sizes of the trees.
Space Complexity: O(N + M), for the preorder traversal strings.
| Approach | Complexity |
|---|---|
| Recursive Tree Traversal | Time Complexity: O(N*M), where N is the number of nodes in the root tree and M is the number of nodes in subRoot tree. |
| Preorder String Comparison | Time Complexity: O(N + M + N*M), where N and M are the sizes of the trees. |
Subtree of Another Tree - Leetcode 572 - Python • NeetCode • 196,060 views views
Watch 9 more video solutions →Practice Subtree of Another Tree with our built-in code editor and test cases.
Practice on FleetCode