Problem
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. Otherwise, return false.A subtree of a binary tree is a node along with all of its descendants.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [3,4,5,1,2]
3
/ \
4 5
/ \
1 2
subRoot = [4,1,2]
4
/ \
1 2
Output
true Input
root = [3,4,5,1,2,null,null,null,null,0]
3
/ \
4 5
/ \
1 2
/
0
subRoot = [4,1,2]
4
/ \
1 2
Output
false Solution
This solution uses Depth-First Search (DFS). We traverse every node in root and check whether the subtree starting at that node is identical to subRoot.To compare two trees, we recursively check whether their corresponding nodes have the same value and structure. If both nodes are
null, they match. If only one is null or their values differ, they do not match.
If the current subtree does not match, the search continues recursively through the left and right subtrees of root.
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
// An empty tree is always a subtree.
if (subRoot == null) {
return true;
}
if (root == null) {
return false;
}
// Check whether the current trees are identical.
if (isSameTree(root, subRoot)) {
return true;
}
// Search in the left and right subtrees.
return isSubtree(root.left, subRoot)
|| isSubtree(root.right, subRoot);
}
private boolean isSameTree(TreeNode p, TreeNode q) {
// Both nodes are null.
if (p == null && q == null) {
return true;
}
// Nodes differ in structure or value.
if (p == null || q == null || p.val != q.val) {
return false;
}
// Compare both subtrees.
return isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}
Complexity
In the worst case, each node in root may be compared with subRoot, resulting in a time complexity ofO(n × m), where n is the number of nodes in root and m is the number of nodes in subRoot.
The recursive call stack can grow up to the height of the trees, resulting in an extra space complexity of
O(h).