Subtree of Another Tree
Problem Statement
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 of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
Constraints:
- 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^4 <= root.val <= 10^4
- -10^4 <= subRoot.val <= 10^4
Input Format:
- Two binary trees represented by their root nodes: root and subRoot
Output Format:
- Return true if subRoot is a subtree of root, and false otherwise
Examples:
Example 1:
Input:
root = [3,4,5,1,2], subRoot = [4,1,2]
Output:
true
Explanation:
The node with value 4 in the root tree is a subtree of the root tree that matches the subRoot tree.
Example 2:
Input:
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output:
false
Explanation:
The node with value 4 in the root tree has a child with value 0, making it different from the subRoot tree.
Solutions
Recursive Approach
Traverse the main tree and for each node, check if the subtree rooted at that node is identical to the given subtree. Use a separate helper function to check if two trees are identical.
String Serialization Approach
Serialize both trees into string representations and check if the serialized subRoot is a substring of the serialized root. This can be efficient with string matching algorithms like KMP.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Start with isSubtree(root=[3,4,5,1,2], subRoot=[4,1,2])
- Check isSameTree(root=[3,4,5,1,2], subRoot=[4,1,2]): Different root values (3 vs 4), return false
- Recursively check left subtree: isSubtree(root=[4,1,2], subRoot=[4,1,2])
- Check isSameTree(root=[4,1,2], subRoot=[4,1,2]): Same values and structure, return true
- Since isSameTree returned true, isSubtree returns true
Hints
Hint 1
Hint 2
Hint 3
Hint 4
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the main tree and the subtree, highlighting potential matching subtrees.
Key visualization elements:
- current node
- matched subtree
- comparison process
Similar Questions
Same Tree
EasyGiven the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Serialize and Deserialize Binary Tree
HardSerialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Implementation Notes
This problem tests understanding of tree traversal and recursive comparison. The recursive approach is more intuitive, while the serialization approach can be more efficient for larger trees with modern string matching algorithms.