Subtree of Another Tree
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.
Walk every node n of root and ask "does the subtree rooted at n equal subRoot?". The inner check is a standard same-tree recursion.
root = [3,4,5,1,2], subRoot = [4,1,2]truedef is_subtree(root, sub_root):
if root is None:
return False
if same(root, sub_root):
return True
return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)
def same(a, b):
if a is None and b is None: return True
if a is None or b is None: return False
if a.val != b.val: return False
return same(a.left, b.left) and same(a.right, b.right)function isSubtree(root, subRoot) {
if (!root) return false;
if (same(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
function same(a, b) {
if (!a && !b) return true;
if (!a || !b) return false;
if (a.val !== b.val) return false;
return same(a.left, b.left) && same(a.right, b.right);
}class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
if (same(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
boolean same(TreeNode a, TreeNode b) {
if (a == null && b == null) return true;
if (a == null || b == null) return false;
if (a.val != b.val) return false;
return same(a.left, b.left) && same(a.right, b.right);
}
}bool same(TreeNode* a, TreeNode* b) {
if (!a && !b) return true;
if (!a || !b) return false;
if (a->val != b->val) return false;
return same(a->left, b->left) && same(a->right, b->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (!root) return false;
if (same(root, subRoot)) return true;
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}Explanation
The question is whether subRoot appears somewhere inside root as an exact copy — same shape and same values. The plan is to try every node of root as a possible matching point.
The function is_subtree walks the big tree. At each node it asks the helper same(root, sub_root): "starting right here, are the two trees identical?" If yes, we found a match. If not, we recurse into the left and right children and try again from there.
The helper same(a, b) is the classic same-tree check. Two trees are equal when both are empty, or both nodes exist with equal values and their left subtrees match and their right subtrees match. Any mismatch returns false immediately.
Example: root = [3,4,5,1,2], subRoot = [4,1,2]. At node 3 the trees differ, so we move on. At node 4 the values, left child 1, and right child 2 all line up perfectly, so same returns true and the answer is true.
In the worst case we compare subRoot against every node, giving roughly O(n * m) work where n and m are the two tree sizes.