A merchandising tool stores the live catalog as a binary tree of categories. Designers save a “featured collection” as another tree. Before a campaign, ops wants a yes/no: does that collection appear as some subtree of the live catalog? The intern called the identity check on the two roots. Matching catalogs returned true. A collection hanging off a child category returned false. The check answered “are they the same tree?”, not “does this tree appear inside that one?”

A tree is a subtree of another if some node in the parent is the same tree as subRoot. The binary tree post owns shape and traversals. The identity walk is already Same Tree. Here we only care about trying that walk at this node, then at the left child, then at the right.

The problem

Given the roots of two binary trees, return whether subRoot appears as a subtree of root — some node in root plus all of that node’s descendants, same structure and equal values. The whole tree is a subtree of itself.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample trees:

      3                    4
     / \                  / \
    4   5                1   2     →  true
   / \
  1   2

      3                    4
     / \                  / \
    4   5                1   2     →  false
   / \
  1   2
     /
    0

[1]                 [1]         →  true
[]                  [1]         →  false
[1]                 []          →  true
[]                  []          →  true

Note: A matching root value is not a hit. The second drawing has the same 4 / 1, 2 keys and an extra 0 under 2, so that candidate is a different tree. Some prompts promise both trees are non-empty. If empty trees are in play: a null subRoot is a subtree of everything, including null; a null root matches only a null subRoot. The two-guard order below is that contract.

Nested identical check from every node is the honest brute force

Walk every node of root. From that node, walk both trees together with the four-way null/value check until they match or disagree. If this candidate fails, try the left child and the right child. Correct. You reinvented the identity walk at every node and did not name it.

boolean isSubtreeNested(TreeNode root, TreeNode subRoot) {
    if (subRoot == null) {
        return true;
    }
    if (root == null) {
        return false;
    }
    if (identicalFromHere(root, subRoot)) {
        return true;
    }
    return isSubtreeNested(root.left, subRoot)
            || isSubtreeNested(root.right, subRoot);
}

boolean identicalFromHere(TreeNode a, TreeNode b) {
    if (a == null && b == null) {
        return true;
    }
    if (a == null || b == null || a.val != b.val) {
        return false;
    }
    return identicalFromHere(a.left, b.left)
            && identicalFromHere(a.right, b.right);
}

The first two guards are the empty contract: null subRoot is true even when root is also null; non-null subRoot against a null root is false. At a dozen nodes this is fine. The intended answer is the same search with the identity walk named and reused, not a different algorithm.

Same Tree at this node, else try the children

If this node is the same tree as subRoot, yes. Otherwise the match, if it exists, hangs off the left or the right. Same Tree owns the paired walk; we call it, we do not re-derive it.

isSubtree(3, 4)
  sameTree(3, 4)  values differ
  isSubtree(4, 4)  sameTree hits on 4 and both children  →  true

The Java is that search. isSameTree is the short helper from Same Tree — call it, do not re-derive the paired walk. || short-circuits so a hit on the left never walks the right.

boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null || q == null) {
        return p == q;
    }
    return p.val == q.val
            && isSameTree(p.left, q.left)
            && isSameTree(p.right, q.right);
}

boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (subRoot == null) {
        return true;
    }
    if (root == null) {
        return false;
    }
    return isSameTree(root, subRoot)
            || isSubtree(root.left, subRoot)
            || isSubtree(root.right, subRoot);
}

Time is O(n · m) — n nodes in root, and a Same Tree walk of up to m nodes in subRoot at each. Space is O(h + s) for the nested frames, heights of root and subRoot. A spine of a million nodes is a million frames; an explicit stack of candidates is the same bound without blowing the JVM stack.

Empty subRoot: first guard, true. Empty root with a non-empty subRoot: second guard, false. Both empty: first guard, true. Whole tree equals subRoot: Same Tree hits at the root, never visits the children. No extra branch.

What interviewers usually poke next

  • Serialize, then substring. Dump both trees with null markers and delimiters, then search one string in the other. Correct if the encoding cannot collide (12 versus 1,2). Follow-up, not the default walk — extra memory, and you still have to get the markers right.
  • Hash each subtree. A Merkle-style fingerprint at every node can make “is this the same tree?” an O(1) map lookup after one pass. Mention it; write it if they ask for O(n + m).
  • Count matches. Same search, add instead of returning on the first hit. Do not start counting inside isSubtree unless they change the contract.
  • Only the two roots. That is Same Tree. A subtree can start below root.

You are done with this problem when you can reject a matching 4 that still has an extra child, and you can name the null-subRoot / null-root returns without a special case beyond those two guards.