Subtree of Another Tree
Easy · Trees · Tree · Depth-First Search · String Matching · Binary Tree · Hash Function
Problem
You are given the roots of two binary trees, root and subRoot. Return True if some node of root is the top of a subtree that is identical to subRoot: the same shape, with the same value in every position. Otherwise return False.
A node's subtree is that node together with all of its descendants, down to the leaves. So a match cannot stop early: if the node in root has a child where subRoot has none, it is not a match. A tree is a subtree of itself.
Tests build both trees from level-order lists with from_level, where None marks a missing child.
Examples
Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: True
The left child of the root, 4, has children 1 and 2 and nothing below them: exactly subRoot.
Input: root = [3,4,5,1,2,None,None,None,None,0], subRoot = [4,1,2] Output: False
The node 4 still has children 1 and 2, but 2 now has a left child 0. The subtree at 4 has four nodes, subRoot has three, so they are not identical.
Constraints
- 1 <= number of nodes in root <= 2000
- 1 <= number of nodes in subRoot <= 1000
- -10^4 <= Node.val <= 10^4
- both trees are at most 500 levels deep (so recursion fits in the browser)
Approaches
- Try every node with a same-tree check — time O(m · n), space O(h)
Follow-up
The node-by-node check can cost O(m · n) when many nodes of root share subRoot's values. Can you make it O(m + n), by serializing both trees or by giving every distinct subtree a number?
Related problems
Start free on Cariara · Coding problems · System design studio
