4.14.6 — Subtree of Another Tree

LeetCode 572 · Easy · ★ Blind 75

The problem

Return true if subRoot appears as a subtree of root. A subtree means a node of root together with all of its descendants — you cannot take a node and only some of what hangs below it.

root:      3          subRoot:   4
         /   \                  / \       →  true
        4     5                1   2
       / \
      1   2

The pattern

Two pieces, and you already have one of them.

1. Are these two trees identical? That is 4.14.5.
2. Try it at every node of root.

The second piece is a straightforward walk. The only thing to be careful about is the base cases.

The solution

Python

class Solution:
    def isSubtree(self, root, subRoot) -> bool:
        if not subRoot:
            return True             # an empty tree is a subtree of anything
        if not root:
            return False            # nothing left to match against

        if self.isSame(root, subRoot):
            return True

        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSame(self, p, q) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        return p.val == q.val and self.isSame(p.left, q.left) and self.isSame(p.right, q.right)

TypeScript

function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  if (!subRoot) return true;
  if (!root) return false;
  if (isSame(root, subRoot)) return true;
  return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

function isSame(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;
  if (!p || !q) return false;
  return p.val === q.val && isSame(p.left, q.left) && isSame(p.right, q.right);
}

Two functions, two jobs. isSubtree searches for a starting point; isSame checks one candidate. Trying to do both in one function is where people tangle themselves — the recursion means two different things and the base cases conflict.

or short-circuits, so once a match is found on the left, the right side is never searched.

Complexity

O(n \cdot m) in the worst case, for a tree of n nodes and a pattern of m. Each of the n nodes may trigger a comparison costing up to m.

In practice it is far better, because most comparisons fail at the first node. The bad case is a tree of identical values, like every node holding 1, where every comparison runs to the end.

The O(n + m) solution

There is a genuinely faster approach, and it is worth knowing because the idea transfers.

Serialise both trees into strings, then ask whether one string contains the other.

The catch, from 4.14.5: a naive traversal string does not determine a tree. So the serialisation must include markers for empty children, and it must delimit values so that 12 cannot match inside 112.

def isSubtree(self, root, subRoot) -> bool:
    def serialise(node) -> str:
        if not node:
            return "#"
        return f",{node.val},{serialise(node.left)}{serialise(node.right)}"

    return serialise(subRoot) in serialise(root)

The leading comma before each value is what stops ,2, matching inside ,12,. Without it, a tree containing 12 would appear to contain 2.

Python's in on strings is roughly linear thanks to a tuned substring search. To make the bound guaranteed you would use KMP (4.31), which gives O(n + m) in the worst case.

Say the simple version first. Then offer this one, and say what makes it correct — the null markers and the delimiters — because that detail is the actual content.

Where this goes next

• Find Duplicate Subtrees (LeetCode 652) — serialise every subtree and count the strings in a hash map. The same serialisation idea used for grouping instead of searching, and it is 4.4.4's fingerprint move applied to trees.
• Merkle trees — hash each subtree from the leaves upward, so comparing two large trees becomes comparing two hashes. That is how Git compares directory trees and how blockchains verify blocks. It is this idea made efficient.

The rule: turning a tree into a string, carefully enough that the string determines the tree, converts tree problems into string problems.

What the interviewer will push on

"Why is it O(n·m), and when is that actually hit?" A tree of repeated values, where comparisons run to completion.

"Can you do better?" Serialise and substring-search, with KMP for a guaranteed bound.

"Why the null markers and the delimiters?" Without nulls the string does not determine the tree; without delimiters 2 matches inside 12.

"Does an empty subRoot count?" Conventionally yes. Ask, because it is genuinely ambiguous and asking is the right move.

One thing to volunteer: mention Merkle trees. It shows the serialisation idea is something you recognise in the wild rather than a trick for this problem.

Next: 4.14.7 Lowest Common Ancestor of a BST — the first problem that uses the search-tree ordering rather than just the shape.