—
candidate
Decide whether subRoot appears as a complete subtree of root. Walk every node of root and, at each one, run a full identical-tree check — a subtree must match shape and values all the way to the leaves.
Given two binary trees root and subRoot, return true if there is a node in root whose subtree is structurally identical to subRoot (same shape, same values, down to every leaf). Example: root=[3,4,5,1,2], subRoot=[4,1,2] → true (the left child of 3 matches). But subRoot=[4,1,2,null,null,0] → false — same head, but the shapes diverge.
subRoot at the current root node and ask are these two whole trees identical? (the sameTree helper). (2) If not, the answer might still be inside the left or right subtree, so recurse. The outer walk finds candidates; the inner sameTree verifies one fully.subRoot is null → true (the empty tree sits inside everything). If root is null but subRoot is not → false (nothing left to match).sameTree(root, subRoot). If it returns true, this node is the answer — done.isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot). Short-circuit on the first hit.sameTree is what enforces that: it keeps descending and only returns true when the entire shape lines up. A common bug is writing sameTree to stop early or to allow a partial overlap — that yields false positives.The straightforward DFS is O(m·n) worst case, but in practice sameTreebails on the first mismatch, so it's far cheaper. The slick linear trick serializes both trees to strings with explicit null markers (so structure can't be confused) and asks whether subRoot's serialization is a substring of root's — solved in O(m+n) with KMP.
sameTree helper is Same Tree (LC 100)verbatim, and the "walk every node and run a check" shape recurs in Symmetric Tree, Path Sum II, and Find Duplicate Subtrees (which serializes subtrees for the same reason).root. Wherever a value equals subRoot's head (4), run a full sameTree check.class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
if (subRoot === null) return true; // empty tree is a subtree of anything
if (root === null) return false; // ran out of root, nothing to match
if (sameTree(root, subRoot)) return true; // anchor here?
return isSubtree(root.left, subRoot) || // else search left
isSubtree(root.right, subRoot); // or right
}
// structural identity: same shape AND same values
function sameTree(a: TreeNode | null, b: TreeNode | null): boolean {
if (a === null && b === null) return true; // both empty → equal
if (a === null || b === null) return false; // one empty → differ
if (a.val !== b.val) return false; // values differ
return sameTree(a.left, b.left) && sameTree(a.right, b.right);
}subRoot is trivially a subtree (the empty tree is everywhere), so return true. If root ran out first while subRoot still has nodes, this branch can't match → false.sameTree(root, subRoot): is the tree rooted right here identical to subRoot? If yes, we found it. This is the only place the actual matching happens.|| short-circuits: the moment the left subtree reports true, we stop.val, then recurse into both pairs of children. It returns true only when shape and values agree everywhere.O(m·n) time worst case (m = nodes in root, n = nodes in subRoot), because sameTree can run from many anchors; O(h) space for the recursion stack (h = height of root). A serialize-plus-KMP solution reaches O(m + n).sameTree at each.| "is X a subtree of Y" | walk Y + sameTree at each node |
| match shape AND values | sameTree: both null / equal val / recurse both kids |
| subRoot is empty | return true (empty ⊆ anything) |
| need O(m+n) | preorder serialize w/ null markers + KMP substring |
function isSubtree(root, subRoot): boolean {
if (!subRoot) return true;
if (!root) return false;
if (sameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
function sameTree(a, b): boolean {
if (!a && !b) return true;
if (!a || !b) return false;
return a.val === b.val && sameTree(a.left, b.left) && sameTree(a.right, b.right);
}isSubtree walk over root, and an inner sameTree that tests full structural identity at a node.