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 <= 104Problem Overview: Given two binary trees root and subRoot, determine whether subRoot appears as a subtree inside root. A subtree means a node in the main tree whose entire structure and node values exactly match subRoot.
Approach 1: Recursive Tree Traversal (DFS Comparison) (Time: O(n * m), Space: O(h))
This approach walks through every node in the main tree and checks if the subtree starting at that node is identical to subRoot. For each node in root, run a second DFS that compares both trees node-by-node. The comparison verifies three things: values match, left children match, and right children match. If any comparison fails, continue scanning other nodes in the main tree.
The key idea is separating the logic into two DFS functions: one that iterates through the main tree and another that checks structural equality. In the worst case, you compare the subtree with every node of the main tree, giving O(n * m) time where n and m are the sizes of the two trees. Recursion depth depends on tree height, so space complexity is O(h). This method is straightforward and commonly used in interviews involving tree and depth-first search problems.
Approach 2: Preorder String Comparison (Tree Serialization) (Time: O(n + m), Space: O(n + m))
This technique converts both trees into strings using preorder traversal. During serialization, include special markers for null nodes so different structures produce different strings. For example, append # whenever a null child appears. Without null markers, different trees could produce identical sequences.
Once both trees are serialized, the subtree check becomes a substring problem. If the preorder string of subRoot appears inside the preorder string of root, the subtree exists. Efficient substring search algorithms such as KMP reduce the complexity to O(n + m). The trade-off is extra memory to store the serialized strings. This method blends ideas from binary tree traversal and string matching algorithms.
Recommended for interviews: The recursive DFS comparison is usually what interviewers expect first because it clearly demonstrates understanding of tree traversal and structural equality checks. Mentioning the serialization approach afterward shows deeper knowledge and awareness of optimization techniques that convert tree problems into string matching problems.
This 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.
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.
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.
We define a helper function same(p, q) to determine whether the tree rooted at p and the tree rooted at q are identical. If the root values of the two trees are equal, and their left and right subtrees are also respectively equal, then the two trees are identical.
In the isSubtree(root, subRoot) function, we first check if root is null. If it is, we return false. Otherwise, we check if root and subRoot are identical. If they are, we return true. Otherwise, we recursively check if the left or right subtree of root contains subRoot.
The time complexity is O(n times m), and the space complexity is O(n). Here, n and m are the number of nodes in the trees root and subRoot, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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. |
| DFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Tree Traversal (DFS comparison) | O(n * m) | O(h) | Most common interview solution. Easy to implement and works well for moderate tree sizes. |
| Preorder String Serialization + Substring Search | O(n + m) | O(n + m) | When you want a more optimized approach by converting the tree comparison into a string matching problem. |
Subtree of Another Tree - Leetcode 572 - Python • NeetCode • 247,953 views views
Watch 9 more video solutions →Practice Subtree of Another Tree with our built-in code editor and test cases.
Practice on FleetCode