Subtree of Another Tree
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 as subRoot.
Examples
root = [3,4,5,1,2], subRoot = [4,1,2]
true
The subtree starting at node 4 matches subRoot.
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
false
The subtree starting at node 4 has an extra node 0.
Constraints
- •
The number of nodes in the root tree is in the range [1, 1000] - •
-10^4 <= Node.val <= 10^4 - •
-10^4 <= subRoot.val <= 10^4
Approaches
For each node in root, check if the subtree matches subRoot.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_subtree(root, subRoot):
def is_same(p, q):
if not p and not q:
return True
if not p or not q:
return False
return p.val == q.val and is_same(p.left, q.left) and is_same(p.right, q.right)
if not root:
return False
if is_same(root, subRoot):
return True
return is_subtree(root.left, subRoot) or is_subtree(root.right, subRoot)Serialize both trees and check substring match.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_subtree(root, subRoot):
def serialize(node):
if not node:
return 'N'
return f'#{node.val},{serialize(node.left)},{serialize(node.right)}'
return serialize(subRoot) in serialize(root)DFS on root, and for each matching node, verify the entire subtree.
Diagram
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_subtree(root, subRoot):
if not subRoot:
return True
if not root:
return False
if root.val == subRoot.val and is_identical(root, subRoot):
return True
return is_subtree(root.left, subRoot) or is_subtree(root.right, subRoot)
def is_identical(p, q):
if not p and not q:
return True
if not p or not q:
return False
return p.val == q.val and is_identical(p.left, q.left) and is_identical(p.right, q.right)Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force - Compare All Subtrees | O(m * n) | O(h) | For each node in root, check if the subtree matches subRoot. |
| DFS with Serialization | O(m * n) | O(m + n) | Serialize both trees and check substring match. |
| Optimized DFS | O(m * n) | O(h) | DFS on root, and for each matching node, verify the entire subtree. |
For each node in root, check if the subtree matches subRoot.
Serialize both trees and check substring match.
DFS on root, and for each matching node, verify the entire subtree.
Common Mistakes
Only checking the root node instead of all possible subtrees
Not verifying the entire subtree structure, just the root value
Forgetting that subRoot can be a single node