LeetCode 572 · Trees

Subtree of Another Tree, explained with a picture

Spotting a small branch pattern inside a big tree.

EasyTrees
▶ Watch it step by step

The problem

Given a big tree and a small tree, decide whether the big tree contains a node whose whole subtree is identical to the small tree.

Input:  big = [3, 4, 5, 1, 2], small = [4, 1, 2]
Output: true

Picture it

Picture holding a stencil shaped like the small tree. We place it on each node of the big tree in turn and check (using the Same Tree test) whether everything below matches the stencil exactly, all the way down to the leaves.

How to recognise it

  • You get a big tree and a small tree and must decide whether the small one appears whole inside the big one.
  • "Whole" means a node in the big tree plus everything below it matches the small tree exactly, down to the leaves. A matching fragment with extra children below does not count.
  • It combines two smaller problems: visit every node of the big tree, and at each one test sameness (the Same Tree check).
  • Up to 2,000 nodes in the big tree and 1,000 in the small one, so even n × m ≈ 2 × 10^6 steps is affordable.

Start with brute force

Write the small tree as a list of tokens with # for empty spots. Then, at every node of the big tree, write out that node's whole subtree the same way and compare the lists.

def ser(node, out):
    if not node:
        out.append("#")
    else:
        out.append(str(node.val))
        ser(node.left, out)
        ser(node.right, out)
    return out

def is_subtree_brute(root, sub):
    target = ser(sub, [])
    def visit(node):
        if not node:
            return False
        return ser(node, []) == target or visit(node.left) or visit(node.right)
    return visit(root)

Each node is written out once for every ancestor, so time is O(n · h + m), where h is the big tree's height: about 2 × 10^6 tokens for a 2,000-node chain. The waste is that a whole subtree is written down even when its very first value already differs from the small tree's root.

From brute force to the idea

  1. Find the waste. Writing the subtree out cannot stop early; a direct comparison can.
  2. Reuse Same Tree. is_same(a, b) walks both trees in step. if not a or not b: return a is b handles the empty cases in one line: it is True only when both are None.
  3. Try every starting point. is_subtree visits the big tree depth-first (DFS: follow one branch to the bottom before trying the next). At each node it asks whether the small tree fits there; if not, it tries the left subtree, then the right.
  4. Stop at the first fit. or short-circuits, so the search ends as soon as one node matches.

This is the key idea: at every node of the big tree, run the Same Tree check; most checks fail on the first value, so the usual cost is far below the worst case.

An O(n + m) method exists: serialise both trees with empty markers and separators, then run a linear-time string search such as KMP (Knuth–Morris–Pratt). It is rarely needed at these sizes.

The key idea

For every node in the big tree, run isSameTree against the small tree. O(m × n) in the worst case.

Python solution

def is_subtree(root, sub):
    if not root:
        return False
    if is_same(root, sub):  # stencil fits?
        return True
    return (is_subtree(root.left, sub) or
            is_subtree(root.right, sub))

def is_same(a, b):
    if not a or not b:
        return a is b          # both empty?
    return (a.val == b.val
            and is_same(a.left, b.left)
            and is_same(a.right, b.right))

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n · h + m): each subtree written out in full, once per ancestorO(n): the token list for the largest subtree
DFS + Same Tree (shown code)O(n · m) worst case: up to m steps at each of n nodes, usually much lessO(h): recursion depth of the big tree (plus the small tree's height)

Edge cases

  • Exact copy: the big tree itself equals the small tree, so the check at the root succeeds.
  • Match with extra children below (big [3, 4, 5, 1, 2, null, null, null, null, 0], small [4, 1, 2]): False, because node 2 has a child 0 in the big tree.
  • Small tree is a single leaf value (big [1, 2, 3], small [2]): True.
  • Empty big tree: False.
  • Empty small tree: the shown code returns False, because a leaf's None children are never tested. LeetCode guarantees at least one node, so this does not arise there.
  • Repeated values: fine; every node is tried, not only the first one with a matching value.

Common mistakes

  • Returning True when only one side is empty in is_same, which accepts a match that has extra nodes below.
  • Stopping at the first node whose value equals the small root, instead of also searching its children.
  • Serialising without separators or empty markers: values 2 and 12 then share text ("12" contains "2"), and different shapes give the same string.
Your turn: count the copies

Return how many nodes of the big tree have a subtree identical to the small tree. For big [1, 1, 1] and small [1] the answer is 2 (the two leaves; the root has children). Describe your approach, then write it if you like.

Compare with our answer

Keep the same DFS with the same is_same check, but do not stop at the first match: add up the matches in both children.

def count_matches(root, sub):
    if not root:
        return 0
    here = 1 if is_same(root, sub) else 0
    return here + count_matches(root.left, sub) + count_matches(root.right, sub)

Time O(n · m) in the worst case, space O(h).

A strong answer mentions: replacing or with a sum so every node is visited, reusing is_same unchanged, and that the root does not count when it has extra children.

Check what stuck

1. You must check whether a big folder tree contains an exact copy of a given small folder structure. Which approach fits best?

2. Why is the shown solution usually much faster than its O(n · m) worst case?

3. A learner writes if not a or not b: return True in is_same. Which input now gets a wrong answer?

Score 60% or more and the lesson is marked complete.