572. Subtree of Another Tree

If you’ve already solved Same Tree, this one is mostly a wrapper around it: try that equality check at every node of the big tree until one lands. Getting there means being precise about what “a subtree” actually means, which is where most first attempts wobble. It’s part of the binary tree patterns family, where “recurse and combine child answers” is the whole game.

The problem

You get two trees, root and subRoot. Return true if subRoot appears somewhere inside root as a subtree — meaning some node in root, together with all of its descendants, is an exact copy of subRoot (same shape, same values). (Full statement on LeetCode.)

The word “all” is the catch. Take root:

    3
   / \
  4   5
 / \
1   2

Against subRoot = [4, 1, 2], the node 4 with its two children 1 and 2 is an exact match, so the answer is true. But if root’s 4 had an extra child hanging off 1, that same subRoot would no longer match there — a subtree drags every descendant along, you can’t stop partway down.

Intuition: match Same Tree at every anchor

Split the problem in two. First, a helper that answers “are these two trees identical?” — that’s exactly Same Tree: walk both in lockstep, node values must agree and both structures must run out at the same time. Second, an outer walk that tries that helper at each node of root as a potential anchor.

Why anchor at every node? Because subRoot could sit anywhere. So at the current node ask: does the tree rooted here equal subRoot? If yes, done. If not, the match — if it exists — must live entirely in the left or right subtree, so recurse into both.

The cost falls out of that description. For each of the $m$ nodes in root, the equality check can scan up to $n$ nodes of subRoot, giving $O(m \cdot n)$ in the worst case (think two long same-valued chains). Space is the recursion depth, $O(h)$ where $h$ is the height of root — up to $O(m)$ for a degenerate tree, $O(\log m)$ when it’s balanced.

Solution

Two small recursions. isSubtree picks anchors; isSameTree decides equality.

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    // Ran out of root without a match. (subRoot is non-null per constraints.)
    if (root == null) return false;
    // Does the tree anchored at this node equal subRoot?
    if (isSameTree(root, subRoot)) return true;
    // Otherwise the match, if any, is deeper on one side.
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

private boolean isSameTree(TreeNode a, TreeNode b) {
    // Both empty here -> the shapes agreed all the way down.
    if (a == null && b == null) return true;
    // One empty, one not -> structures diverge.
    if (a == null || b == null) return false;
    return a.val == b.val
        && isSameTree(a.left, b.left)
        && isSameTree(a.right, b.right);
}

The || in isSubtree short-circuits: the moment a match turns up, the rest of the tree is never touched. And the a == null && b == null line in isSameTree is what enforces “all descendants” — a subtree that’s a prefix of the pattern (or vice versa) fails because one side hits null while the other still has nodes.

Complexity

	Time	Space
Recursive match	$O(m \cdot n)$	$O(h)$

Here $m$ is the node count of root, $n$ that of subRoot, and $h$ the height of root. There’s a slicker $O(m + n)$ route — serialize both trees and run a string search (KMP) — but it needs careful null and delimiter handling to avoid false hits like 12 matching inside 123, and interviewers rarely require it for the Easy tag.

In an interview

Say the decomposition out loud before coding: “I’ll write a Same Tree equality check, then call it at every node of root.” That framing signals you spotted the reuse, which is the point of this problem. Then write isSameTree first — it’s the piece doing the real work.

The trap is the null handling in the equality check. Folks write if (a == null || b == null) return false; before handling the both-null case, which wrongly rejects two empty subtrees and quietly breaks matches near the leaves. Order matters: both-null returns true, then one-null returns false.

This leans directly on Same Tree — solve that first if you haven’t — and the “recurse into children, combine their answers” shape is the backbone of the whole binary tree patterns set, from Maximum Depth to Invert Binary Tree.

References

• LeetCode 572 — Subtree of Another Tree