Subtree of Another Tree

EasyTree recursionLeetCode 572 ↗World 3-6

0:00 / 0:00

Check if one binary tree appears inside another. Try every node as a starting point and run a same-tree check from there.

▼

The problem

LeetCode 572 (Easy). Given the roots of two binary trees root and subRoot, return true if there is a node in root whose subtree (that node and all its descendants) has the same structure and the same values as subRoot.

Examples (LeetCode's): root = [3,4,5,1,2], subRoot = [4,1,2] → true; root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] → false (node 2 has an extra child 0, so the subtree at 4 doesn't match all the way down).

TRY IT ON LEETCODE ▶

The solution

def isSubtree(root, subRoot):
    if not root:
        return False
    if sameTree(root, subRoot):
        return True
    return (isSubtree(root.left, subRoot) or
            isSubtree(root.right, subRoot))

def sameTree(a, b):
    if not a and not b:
        return True
    if not a or not b or a.val != b.val:
        return False
    return (sameTree(a.left, b.left) and
            sameTree(a.right, b.right))

Transcript

Subtree of Another Tree. Picture both trees as constellations: a big star chart and a small glass template. Is the template in the chart, rooted at some star, with every star below it?

The chart is three, four, five, one, two; the template is four, one, two. Lay it on star four: it all matches. True. Now give star two a child, zero. The template ends at two, but the chart keeps going. False.

Matching only values isn't enough: four, one and two are still there. Matching only the shape fails too. Values and shape must match all the way down.

So try every star as a start, and run a same tree check there. Two trees are the same when both are empty, or their roots match and both pairs of subtrees are the same.

In code, isSubtree walks the chart. If sameTree matches here, return true; else try left, then right. sameTree is true when both nodes are empty, false when only one is or the values differ, and otherwise checks both sides.

Second chart: at star three, the values differ. At star four, four, one and two match, but two has a zero where the template has nothing. Stars one, two, zero and five fail at once. False.

With m stars in the chart and n in the template, that's order m times n time at worst, and order h stack space. Serializing both trees and matching strings with KMP gets order m plus n.

Every star, same tree. That's Subtree of Another Tree.