Watch 10 video solutions for Subtree of Another Tree, a easy level problem involving Tree, Depth-First Search, String Matching. This walkthrough by NeetCode has 247,953 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |