Subtree of Another Tree

EasyTreesTreeDFSBinary TreeString Matching

Problem

You are given the roots of two binary trees, a larger tree and a candidate subtree. Determine whether the candidate appears somewhere inside the larger tree as an exact subtree: some node in the larger tree, together with everything below it, must match the candidate's shape and values exactly.

Example. A larger tree rooted at 3 with left child 4 (children 1 and 2) and right child 5 contains the candidate tree rooted at 4 with children 1 and 2 as a subtree, since node 4 and everything beneath it matches exactly.

Key idea

This builds directly on checking whether two trees are identical. A naive attempt might match values loosely wherever they occur, but a real match requires exact structural equality starting at some single node.

So combine two traversals. Walk the larger tree looking for a starting point: at every node, test whether the subtree rooted there is identical, same shape and values, to the candidate, using the same paired-recursion equality test used for comparing two whole trees. If any node passes, the answer is yes; if none do, it is no. Each identity check only costs work proportional to the candidate's size, since it fails fast on the first mismatch. A faster alternative serializes both trees into strings, encoding null children distinctly, and checks for a substring match, but the direct recursive check is simpler to reason about correctly.

Solution

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) {
    // an empty candidate tree is trivially a subtree of anything
    return true;
  }

  if (root === null) {
    return false;
  }

  // this node is a valid match only if everything below it equals subRoot exactly
  if (isIdentical(root, subRoot)) {
    return true;
  }

  // otherwise keep looking for a matching root elsewhere in the tree
  return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

// same paired comparison used to check whether two whole trees are identical
function isIdentical(a: TreeNode | null, b: TreeNode | null): boolean {
  if (a === null && b === null) {
    return true;
  }

  if (a === null || b === null || a.val !== b.val) {
    return false;
  }

  return isIdentical(a.left, b.left) && isIdentical(a.right, b.right);
}

Complexity

  • Time: O(m times n). In the worst case, an identity check of size m runs at each of the n nodes of the larger tree.
  • Space: O(h). Recursion depth from walking the larger tree, plus the smaller depth of the identity check itself.

Watch out for

  • Matching only values without checking shape allows false positives; the identity check must treat null children as meaningful positions, not gaps to skip.
  • An empty candidate tree is trivially a subtree of anything.
  • Stopping at the first similar-looking node without a full identity check gives wrong answers on trees with repeated values.

Pattern

This is an identity check nested inside a search: reuse a simpler exact-match routine as the test applied at every candidate position in a larger structure. That combination is why this problem is also framed as a tree analogue of substring search.

Related questions