Subtree of Another Tree
The key idea
A subtree match means: find a node in
root whose ENTIRE subtree is identical to subRoot. So combine two ideas — walk every node of root as a candidate root, and at each candidate run an exact same-tree check that compares both trees node-for-node in lockstep.Problem
You are 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, and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of that node's descendants. The tree tree could also be considered as a subtree of itself.
Constraints
- The number of nodes in
rootis in the range[1, 2000]. - The number of nodes in
subRootis in the range[1, 1000]. -10^4 <= Node.val <= 10^4
Examples
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Complexity
Time: O(m * n) Space: O(m + n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY