Subtree of Another Tree

EASY✓ CHIP-TIMEDLC #572 — FULL STATEMENT ↗

The drill: Decide whether one binary tree appears anywhere inside another, rooted at some node — same shape and values from that node down, exactly.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two binary trees arrive — a larger one and a candidate — and the task is to decide whether the candidate appears somewhere inside the larger tree, rooted at some node within it.

"Appears" means an exact match from that starting node downward: the same values in the same shape, with no extra or missing children anywhere in that portion of the larger tree.

The candidate matching the larger tree's root counts just as well as matching some node buried deeper — the whole larger tree is fair game as a starting point for the comparison.

EX 01

root = [4] · subRoot = [4]

→ true

TWO MATCHING SINGLE NODES

EX 02

root = [4] · subRoot = [5]

→ false

TWO SINGLE NODES, DIFFERENT VALUE

EX 03

root = [3, 4, 5, 1, 2] · subRoot = [4, 1, 2]

→ true

TARGET MATCHES A LEFT SUBTREE EXACTLY

the larger tree can hold up to a few thousand nodes, the candidate up to a few hundred
node values can be negative, zero, or positive
a match must be exact from the matching node downward, not merely value-similar

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

'Appears somewhere' means checking every node of the big tree as a possible starting point. What check do you already know for 'do these two trees match exactly'?

HINT 2 THE STRUCTURE

At each node of the big tree, ask: does the subtree rooted here match the target tree exactly? If not, move on and ask the same question of its children.

HINT 3 ONE STEP FROM THE ANSWER

That's O(n·m) in the worst case. To do better, flatten both trees into strings — with a null marker for every missing child, so shapes can't be confused — and ask whether one string contains the other.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SERIALIZED SEARCHPATTERN · SERIALIZE AND SEARCHroot = [3, 4, 5, 1, 2] · subRoot = [4, 1, 2]

STEP 1

Serialize both trees with null markers so shape can't be faked, then check whether the target's signature is a substring of the big tree's. Start by encoding the target: root 4, left 1, right 2.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/subtree-of-another-tree.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def serialize(node):
            if not node:
                return ",#"
            return "," + str(node.val) + serialize(node.left) + serialize(node.right)

        return serialize(subRoot) in serialize(root)

TIME O(N+M)SPACE O(N+M)PYTHON · RACE PACE · 8 LN

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def same(a, b):
            if not a and not b:
                return True
            if not a or not b:
                return False
            return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)

        if not root:
            return subRoot is None
        if same(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

TIME O(N·M)SPACE O(H)PYTHON · TRAINING PACE · 14 LN

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return serialize(root).contains(serialize(subRoot));
    }

    private String serialize(TreeNode node) {
        if (node == null) {
            return ",#";
        }
        return "," + node.val + serialize(node.left) + serialize(node.right);
    }
}

TIME O(N+M)SPACE O(N+M)JAVA · RACE PACE · 12 LN

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return subRoot == null;
        }
        if (same(root, subRoot)) {
            return true;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean same(TreeNode a, TreeNode b) {
        if (a == null && b == null) {
            return true;
        }
        if (a == null || b == null) {
            return false;
        }
        return a.val == b.val && same(a.left, b.left) && same(a.right, b.right);
    }
}

TIME O(N·M)SPACE O(H)JAVA · TRAINING PACE · 21 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED