Subtree of Another Tree
You're given the roots of two non-empty binary trees, root and subRoot. Return true if some node in root, together with all of its descendants, has exactly the same structure and values as subRoot, and false otherwise. The match must run all the way down to the leaves, so extra nodes below it rule it out. A tree counts as a subtree of itself.
Examples
root = [3,4,5,1,2], subRoot = [4,1,2] returns true
The node 4 in root has children 1 and 2, and neither has children of its own, so that subtree matches subRoot exactly.
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] returns false
Node 4 starts out the same, but its child 2 has a child 0 that subRoot lacks, so the subtree doesn't match. No other node has value 4.
Constraints
- 1 <= number of nodes in root <= 2000
- 1 <= number of nodes in subRoot <= 1000
- -10^4 <= Node.val <= 10^4
Hints
If you already knew how to check whether two trees are identical, where would you need to run that check?
Depth-first search over root, calling a Same Tree helper at every node.
isSubtree(node): if node is null return false; if sameTree(node, subRoot) return true; otherwise return isSubtree(node.left) or isSubtree(node.right). sameTree returns true when both are null, false when only one is, and otherwise compares values and both pairs of children.
Drill This: Your Approach First
Approach
Use depth-first search (DFS) over root, and at each node ask whether the tree starting there is the same tree as subRoot. That check is the Same Tree problem: two trees match when both are empty, or both roots have equal values and their left and right subtrees match. Return true as soon as any node matches. Each of the m nodes in root can start a comparison of up to n nodes from subRoot, giving O(m * n) time; the recursion never goes deeper than root's height h.
Time
O(m * n)
Space
O(h)
Pitfall
Solutions
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
if (sameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean sameTree(TreeNode a, TreeNode b) {
if (a == null || b == null) return a == b;
return a.val == b.val && sameTree(a.left, b.left) && sameTree(a.right, b.right);
}
}from typing import Optional
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not root:
return False
if self.sameTree(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
def sameTree(self, a, b) -> bool:
if not a or not b:
return a is b
return a.val == b.val and self.sameTree(a.left, b.left) and self.sameTree(a.right, b.right)