Subtree of Another Tree
Problem
Given two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values as subRoot, otherwise return false.
- The number of nodes in the root tree is in the range [1, 2000]
- The number of nodes in the subRoot tree is in the range [1, 1000]
- −10⁴ ≤ root.val ≤ 10⁴
- −10⁴ ≤ subRoot.val ≤ 10⁴
Example
root = [3,4,5,1,2], subRoot = [4,1,2]trueThe subtree rooted at the node with value 4 in root matches subRoot exactly. The algorithm recursively checks if root and subRoot are identical starting at the root node. It finds they are not, so it recursively checks the left and right subtrees of root. When it reaches the node with value 4, it invokes the isSameTree helper, which confirms the two trees are identical in structure and values, returning true.
Approach
Straightforward Solution
A brute-force approach would check every node in root as a potential subtree root and compare it to subRoot. This involves a recursive traversal of root and, for each node, a recursive comparison with subRoot, resulting in O(m*n) time complexity where m and n are the sizes of root and subRoot respectively.
Core Observation
A subtree match requires two conditions: the subtree rooted at some node in root must be structurally identical to subRoot, and all corresponding node values must be equal. This naturally suggests a recursive tree comparison.
Path to Optimal
The problem breaks down into two recursive tasks: (1) traverse root to find candidate nodes, and (2) for each candidate, check if the subtree matches subRoot exactly. The helper function isSameTree performs the subtree equality check by recursively comparing nodes. The main function isSubtree uses this helper to check the current node and then recursively checks left and right children if no match is found. This approach is straightforward and optimal given the problem constraints.
Optimal Approach
Use a depth-first search (DFS) to traverse every node in root. At each node, invoke a helper function isSameTree to check if the subtree rooted at that node matches subRoot. The isSameTree function recursively compares nodes for equality in value and structure. If a match is found, return true immediately; otherwise, continue searching the left and right subtrees. This guarantees correctness and runs in O(m*n) time in the worst case.
Time
O(m * n)
In the worst case, for each of the m nodes in root, the algorithm calls isSameTree which can take up to O(n) time to compare subtrees of size n, resulting in O(m * n) total time.
Space
O(h)
The auxiliary space is O(h), where h is the height of the root tree, due to the recursion stack during DFS traversal and subtree comparison. This does not include input or output space.
Pattern Spotlight
DFS (Recursive Tree Traversal and Comparison)
When checking if one tree is a subtree of another, recursively traverse the larger tree and at each node perform a recursive equality check; this dual-recursion approach leverages DFS to explore all candidate roots and verify subtree identity efficiently.
Solution
| 1 | class Solution:
|
| 2 | def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
|
| 3 | if not subRoot:
|
| 4 | return True
|
| 5 | if not root:
|
| 6 | return False
|
| 7 |
|
| 8 | if self.isSameTree(root, subRoot):
|
| 9 | return True
|
| 10 |
|
| 11 | return (self.isSubtree(root.left, subRoot) or
|
| 12 | self.isSubtree(root.right, subRoot))
|
| 13 |
|
| 14 | def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
|
| 15 | if not p and not q:
|
| 16 | return True
|
| 17 | if not p or not q or p.val != q.val:
|
| 18 | return False
|
| 19 |
|
| 20 | return (self.isSameTree(p.left, q.left) and
|
| 21 | self.isSameTree(p.right, q.right)) |
| 1 | class Solution { |
| 2 | public boolean isSubtree(TreeNode root, TreeNode subRoot) { |
| 3 | if (subRoot == null) { |
| 4 | return true; |
| 5 | } |
| 6 | if (root == null) { |
| 7 | return false; |
| 8 | } |
| 9 | |
| 10 | if (isSameTree(root, subRoot)) { |
| 11 | return true; |
| 12 | } |
| 13 | |
| 14 | return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); |
| 15 | } |
| 16 | |
| 17 | private boolean isSameTree(TreeNode p, TreeNode q) { |
| 18 | if (p == null && q == null) { |
| 19 | return true; |
| 20 | } |
| 21 | if (p == null || q == null || p.val != q.val) { |
| 22 | return false; |
| 23 | } |
| 24 | |
| 25 | return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); |
| 26 | } |
| 27 | } |
Step-by-Step Solution
Return True Immediately if subRoot is Empty
| 3 | if not subRoot:
|
| 4 | return True
|
Objective
To handle the edge case where subRoot is None, which by definition is a subtree of any tree.
Key Insight
An empty tree is a subtree of any tree, so the algorithm can immediately return true if subRoot is None. This early return simplifies the recursive logic by handling this trivial case upfront.
Interview Quick-Check
State & Boundaries
Check if subRoot is None before any other logic, as this is a base case that guarantees a positive result.
Common Pitfalls & Bugs
Failing to handle an empty subRoot can lead to incorrect false negatives.
Return False if root is Empty but subRoot is Not
| 5 | if not root:
|
| 6 | return False
|
Objective
To handle the edge case where root is None but subRoot is not, meaning subRoot cannot be a subtree.
Key Insight
If root is None but subRoot is not, there is no subtree in root that can match subRoot. Returning false immediately prevents unnecessary recursion and correctly handles this boundary condition.
Interview Quick-Check
State & Boundaries
Check if root is None after confirming subRoot is not None to correctly handle the absence of any subtree.
Check if Current Trees are Identical Using isSameTree
| 8 | if self.isSameTree(root, subRoot):
|
| 9 | return True
|
Objective
To determine if the subtree rooted at the current node in root matches subRoot exactly.
Key Insight
The isSameTree helper recursively compares two trees node-by-node for structural and value equality. If they match, the current subtree is the desired subtree, and the algorithm returns true immediately, avoiding further unnecessary traversal.
Interview Quick-Check
Core Logic
Use a recursive helper to check if two trees are identical by comparing root values and recursively checking left and right subtrees.
State & Boundaries
Return true if both nodes are None, false if only one is None or values differ.
Recursively Search Left and Right Subtrees for Matching Subtree
| 11 | return (self.isSubtree(root.left, subRoot) or
|
| 12 | self.isSubtree(root.right, subRoot))
|
Objective
To continue searching for subRoot in the left and right children of the current root node if the current subtree does not match.
Key Insight
Since the subtree can start at any node, if the current node's subtree does not match, the algorithm recursively searches the left and right subtrees. The use of logical OR ensures that if either subtree contains subRoot, the function returns true.
Interview Quick-Check
Core Logic
Recursively check left and right subtrees for subRoot, returning true if either contains the subtree.
State & Boundaries
Use short-circuit evaluation to avoid unnecessary recursion once a match is found.
Define Helper to Compare Two Trees for Exact Equality
| 14 | def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
|
Objective
To define a reusable helper that determines whether two trees are structurally identical and equal in node values.
Key Insight
The main subtree search should not duplicate full tree-equality logic inline. Separating exact-equality comparison into its own helper makes the search logic clean: traverse root for candidates, then invoke a precise tree-comparison routine when needed.
Interview Quick-Check
Core Logic
Separate subtree search from exact tree comparison so each recursive function has a single job.
State & Boundaries
The helper must compare both structure and values, not just root values.
Common Pitfalls & Bugs
If the helper is missing or incomplete, the algorithm can report false positives from partial matches.
Recursively Compare Two Trees for Structural and Value Equality
| 15 | if not p and not q:
|
| 16 | return True
|
| 17 | if not p or not q or p.val != q.val:
|
| 18 | return False
|
| 20 | return (self.isSameTree(p.left, q.left) and
|
| 21 | self.isSameTree(p.right, q.right)) |
Objective
To verify if two trees are exactly the same by recursively comparing node values and their left and right subtrees.
Key Insight
The isSameTree function uses DFS to check if both trees are empty (base case for equality), or if one is empty or values differ (base case for inequality). Otherwise, it recursively compares left and right children. This ensures a thorough structural and value comparison, which is essential for confirming subtree identity.
Interview Quick-Check
Core Logic
Check base cases for None nodes and value equality, then recursively verify left and right subtrees.
State & Boundaries
Return true only if both left and right subtree comparisons return true.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if self.isSameTree(root, subRoot):Check if the current root and subRoot trees are identical.
This is the critical check that determines if the subtree rooted at the current node matches subRoot exactly, enabling early termination if true.
return TrueReturn true if the current trees are identical.
Returning immediately upon finding a match avoids unnecessary further traversal, improving efficiency.
if not p and not q:Check if both nodes are None, indicating identical empty trees.
This base case confirms that two empty trees are identical, forming the foundation of the recursive equality check.
if not p or not q or p.val != q.val:Check if either node is None or their values differ.
This condition detects structural or value mismatches, allowing early pruning of non-matching subtrees.
self.isSameTree(p.right, q.right))Recursively compare right children and combine with left subtree result.
Both left and right subtrees must match for the trees to be identical; the logical AND enforces this strict equality.
if not subRoot:Check if subRoot is None, indicating an empty subtree.
An empty tree is a subtree of any tree by definition, so returning true here handles this trivial base case immediately.
if not root:Check if root is None while subRoot is not None.
If root is empty but subRoot is not, subRoot cannot be a subtree, so the function must return false.
return (self.isSubtree(root.left, subRoot) orRecursively check if subRoot is a subtree of root's left child.
If the current node's subtree does not match, the algorithm explores the left subtree as a potential match location.
self.isSubtree(root.right, subRoot))Recursively check if subRoot is a subtree of root's right child and combine with left subtree result.
The logical OR ensures that if either subtree contains subRoot, the function returns true, covering all possible subtree locations.
return TrueReturn true if both nodes are None.
This return terminates recursion for matching empty subtrees, ensuring correctness.
return FalseReturn false if nodes differ in presence or value.
Returning false here prevents further unnecessary recursion down invalid paths.
return (self.isSameTree(p.left, q.left) andRecursively compare left children of both trees.
This recursive call ensures the left subtrees are identical, a necessary condition for overall tree equality.
return TrueReturn true if subRoot is None.
This early return prevents unnecessary recursion and simplifies the main logic by handling the empty subtree case upfront.
return FalseReturn false if root is None and subRoot is not.
This prevents further recursion on an empty tree and correctly handles the boundary condition where no subtree can exist.
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:Define the helper that checks whether two trees are exactly the same.
This helper isolates exact tree-comparison logic so the main DFS can focus only on scanning candidate subtree roots.
Test Your Understanding
Why does the algorithm need to check both the current node and recursively its left and right children when searching for the subtree?
Because the subtree can start at any node in root, the algorithm must check every node as a potential root of the subtree. Checking only the current node is insufficient; recursively exploring left and right children ensures all possible subtree roots are considered.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Subtree of Another Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Subtree of Another Tree drill