Subtree of Another Tree
The Prompt
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 tree `t` is a tree consisting of a node in `t` and all of its descendants.
Understanding the Problem
You are asked whether subRoot appears somewhere inside root as a complete subtree: some node of root, together with ALL of its descendants, must exactly equal subRoot. Matching just a prefix of a subtree does not count.
That decomposes into two familiar pieces: walk every node of root (DFS), and at each node run a same-tree check against subRoot. If any anchor node passes the full equality check, the answer is true.
The Interview Flow
Interviewer
Given two trees, a main tree and a potential subtree, how do you check if the second is a subtree of the first?
Candidate
I can leverage the solution from the "Same Tree" problem. I need to traverse the main tree and for each node, check if the subtree rooted at that node is identical to the given `subRoot` tree.
Interviewer
So you'll need a helper function?
Candidate
Yes, a helper function `isSameTree(t1, t2)` would be perfect. My main function `isSubtree(root, subRoot)` would then work as follows: the base case is if `root` is null, I return false. Then, I check if `isSameTree(root, subRoot)` is true. If it is, I've found it and can return true.
Interviewer
And if it's not the same tree at the current node?
Candidate
If it's not a match at the current node, then the subtree might exist in the left or right children of the main tree. So I would recursively call `isSubtree(root.left, subRoot)` OR `isSubtree(root.right, subRoot)`. If either of those calls returns true, then the overall result is true.
Interviewer
That logic is sound. It correctly checks every possible starting node in the main tree. Please implement it.
Why is "same-tree at every node" enough?
If subRoot occurs anywhere, it is rooted at some specific node of root — and the outer DFS visits every node, so that anchor is guaranteed to be tried. The inner same-tree check enforces exact structure and values all the way down, so false positives from partial matches are impossible. The invariant: after visiting a node and failing, no subtree anchored at that node equals subRoot.
Worst case runs the O(m) equality check at each of n nodes: O(n × m) time, O(h) space for the recursion. Mentioning the serialization + string-matching or Merkle-hash improvements is a nice follow-up in interviews.
Recursive Solution with a Helper
- First, implement the `isSameTree(p, q)` helper function as in the "Same Tree" problem. This function will be our tool for comparison.
- Now, in the main `isSubtree(root, subRoot)` function:
- Handle the base cases: If `subRoot` is null, it is technically a subtree of any tree, so return `true`. If `root` is null (but `subRoot` is not), return `false`.
- Check for a match at the current node: If `isSameTree(root, subRoot)` is `true`, we are done, return `true`.
- If no match is found at the current node, the subtree must be located in either the left or right child. Make recursive calls:
- Return the result of `isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)`.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function isSubtree(root, subRoot) {
if (!subRoot) return true;
if (!root) return false;
if (isSameTree(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q || p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}Explanation
Search for subRoot = [4, 1, 2] inside root = [3, 4, 5, 1, 2] — each node of root is tried as an anchor.
1The two inputs. DFS over root will try each node as a potential anchor for a same-tree match against subRoot.
2Anchor at 3: sameTree fails immediately (3 ≠ 4). Keep walking — recurse into the children of 3.
3Anchor at 4: values match (4 = 4, 1 = 1, 2 = 2) and both leaves have matching null children — an exact subtree. Return true.
Complexity Analysis
TIME
O(m*n)
SPACE
O(h_m)
Finished working through this one?
Mark it complete to track it on your Data Structures path.