Subtree of Another Tree (LeetCode 572)

The problem

You get two binary trees, root and sub. Return True if root contains a node whose entire subtree is identical to sub (same shape and same values, all the way down to the leaves). A tree counts as a subtree of itself.

Input:  root = [3, 4, 5, 1, 2], sub = [4, 1, 2]

        3              4
       / \            / \
      4   5          1   2
     / \
    1   2

Output: True

The subtree rooted at node 4 in root is exactly sub.

If node 2 in root had an extra child (say 0), the answer would be False: the subtree at 4 must match sub completely, not just start the same way.

How to think about it

Start with brute force, because it’s already good enough. A matching subtree has to start somewhere. So try every node of root as the starting point and ask: “is the tree rooted here the same as sub?” That question is exactly Same Tree, which you already know how to answer.

The key insight: compose two DFS functions. An outer DFS walks every node of root. An inner DFS (same) compares two trees in lockstep. The outer one returns True if the current node matches, or if sub is a subtree of the left child, or of the right child.

Is there something faster? Yes: serialise both trees with null markers and run a string-matching algorithm, or hash every subtree, for O(n + m). Mention it in an interview, but the O(n·m) version is what most interviewers expect for an Easy, and it’s far less error-prone to write.

Which pattern is this? Tree DFS. The tell is “does tree B appear inside tree A”, which breaks into “is it here, or in the left subtree, or in the right subtree”.

Approach

1. Define same(a, b): both empty is True; one empty or values differ is False; otherwise compare left with left and right with right.
2. If root is empty, return False (a non-empty sub can’t fit).
3. If same(root, sub), return True.
4. Otherwise return whether sub is a subtree of root.left or of root.right.

Solution

def is_subtree(root, sub):
    def same(a, b):                                          # the Same Tree check
        if not a and not b: return True
        if not a or not b or a.val != b.val: return False
        return same(a.left, b.left) and same(a.right, b.right)
    if not root: return False
    if same(root, sub): return True                          # does it match starting here?
    return is_subtree(root.left, sub) or is_subtree(root.right, sub)   # else look deeper
# is_subtree(tree[3,4,5,1,2], tree[4,1,2]) -> True

Dry run

On the example:

The right child 5 is never checked, because or short-circuits.

Complexity

• Time: O(n·m) worst case, where n and m are the sizes of root and sub. For each of the n nodes, same may compare up to m nodes before failing. In practice most same calls fail at the first value.
• Space: O(h). The deepest recursion is the outer DFS depth plus the inner same depth, both bounded by tree height.

Edge cases and pitfalls

• Must match to the leaves. Starting the same way isn’t enough; the extra-child case above must return False.
• Duplicate values. root may contain several nodes equal to sub’s root. Don’t stop at the first value match; if same fails there, keep searching.
• Naive serialisation bug. If you serialise without separators, "12" and "2" look like a match. Always add delimiters and null markers.
• Empty root returns False for a non-empty sub.

Related problems

• Same Tree (LeetCode 100): the inner helper, on its own.
• Serialize and Deserialize Binary Tree (LeetCode 297): the serialisation behind the faster O(n + m) approach.
• Find the Index of the First Occurrence in a String (LeetCode 28): the string matching that serialised trees reduce to.