Problem overview
IsSubtree receives two binary trees, root and subRoot, and returns a bool: is there a node in root whose whole subtree, that node and every descendant, is exactly subRoot? "Exactly" means the same shape and the same value in every position. The lesson provides the TreeNode class (val, left, right), as the starter code's comment shows.
With root = [3,4,5,1,2] and subRoot = [4,1,2], the node 4 with its children 1 and 2 matches, so the answer is true. If the 2 also had a child 0, the answer would be false: a subtree takes every descendant of its node, so no node of root gives back subRoot. A tree is also a subtree of itself, and with root = [1,1] and subRoot = [1] the answer is true, because the left child 1 has nothing below it.
Approach: try every node as the starting point
Split the question in two:
- Given two trees, are they identical? A helper,
IsSameTree, answers that. - Which node of
rootshould be compared withsubRoot? Any of them might be the one, so try all.
The second part is a recursion over root: subRoot is a subtree of root if it equals the tree at root itself, or if it is a subtree of the left child, or of the right child. This visits every node once as a candidate starting point.
Each comparison stops as soon as the trees differ, and it can never go past the size of subRoot, because a comparison only continues while both trees still have nodes. With n nodes in root and m in subRoot, there are at most n comparisons of at most m nodes each: O(n * m) time.
Step by step
The lesson writes IsSubtree first, assuming the helper exists, and then the helper.
- Base case:
root == nullreturnsfalse. An empty tree has no node wheresubRootcould start, andsubRootalways has at least one node. This check also ends the recursion when it steps past a leaf. - Compare at
rootitself. IfIsSameTree(root, subRoot)is true, returntrueand stop searching. - Otherwise search lower. Return
IsSubtree(root.left, subRoot) || IsSubtree(root.right, subRoot). The||operator skips the right side when the left side already found a match. - Write
IsSameTree(TreeNode p, TreeNode q), returningbool. - Both null means equal. Two empty trees are the same tree. This also ends the recursion when both sides run out at the same moment.
- Exactly one null means different. Both-empty was handled above, so if either is
null, one tree has a node where the other has none: the shapes differ. - Different values mean different trees. Both nodes exist here, so reading
p.valandq.valis safe. - Compare the children. The roots match, so the trees are the same exactly when the left subtrees are the same and the right subtrees are the same: two recursive calls joined with
&&.
The solution in C#
class Solution {
public bool IsSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
}
public bool IsSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return false;
}
if (IsSameTree(root, subRoot)) {
return true;
}
return IsSubtree(root.left, subRoot) || IsSubtree(root.right, subRoot);
}
}
C# details worth knowing:
nulland reference types.TreeNodeis a class, so a variable of that type holds a reference, and a missing child isnull. Writingp.valwhenpisnullthrowsNullReferenceException, which is why thenullchecks come before the value check.==on nodes compares references.TreeNodedoesn't define its own equality, sop == qwould ask whether both variables point at the very same object, not whether the trees look alike. That is why the value comparison is written out by hand.- Short-circuit operators.
&&and||evaluate their right side only when needed. InIsSameTreethis means a difference found on the left prevents any work on the right. - Method names are PascalCase. C# convention (and the lesson's tests) use
IsSubtreeandIsSameTree, while the node fields keep the lowercase namesval,leftandright.
Complexity
Time: O(n * m). IsSubtree reaches each of the n nodes of root once. At each one, IsSameTree visits at most m node pairs, because it only goes deeper while both trees still have nodes. In practice most comparisons end at the first mismatching value.
Space: O(h) for the call stack, where h is the height of root. IsSubtree goes at most that deep, and IsSameTree never goes deeper than the height of subRoot. A tree that is a straight line makes h equal to n; the lesson limits depth to 400 levels, which is safe for recursion.
Edge cases and common mistakes
- A tree is a subtree of itself.
root = [1]andsubRoot = [1]returnstrue, because the check atrootcomes first. - Matching values is not enough. With
root = [1,2]andsubRoot = [2,3]the result isfalse. And withroot = [1,null,2]andsubRoot = [1,2]it is alsofalse: the 2 is a right child in one tree and a left child in the other. - Extra descendants. Checking only that
subRoot's nodes appear somewhere below a node is wrong. Example 2 has the right values below the 4, but the extra 0 makes the trees different.IsSameTreehandles this because a node with a child facing a node without one hits the "exactly onenull" check. - Forgetting the base case in
IsSubtree. Without theroot == nullcheck, the recursion would pass anulltoIsSameTree, and thenIsSubtree(root.left, ...)would throw whenrootisnull. - Mixing up
&&and||. Comparing children needs both sides to match (&&); searching for the start needs only one side to contain the match (||).
Testing
Building the trees in a small program and calling IsSubtree gives these results:
| root | subRoot | Result |
|---|---|---|
[3,4,5,1,2] | [4,1,2] | True |
[3,4,5,1,2,null,null,null,null,0] | [4,1,2] | False |
[1,1] | [1] | True |
[1] | [1] | True |
[1,2] | [2,3] | False |
[1,null,2] | [1,2] | False |
