Same Tree

EASY✓ CHIP-TIMEDLC #100 — FULL STATEMENT ↗

The drill: Decide whether two binary trees are identical — same values arranged in exactly the same shape, not just the same values somewhere.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two binary trees arrive, and the task is to decide whether they're truly identical — the same values arranged in exactly the same shape, node for node.

Matching values alone isn't enough: a node present in one tree but missing in the other at the corresponding spot breaks the match, even if every value that does exist lines up perfectly.

Two empty trees count as identical to each other, and an empty tree never matches a non-empty one, no matter what values the non-empty one holds.

EX 01

p = [] · q = []

→ true

TWO EMPTY TREES

EX 02

p = [] · q = [1]

→ false

EMPTY AGAINST A SINGLE NODE

EX 03

p = [1] · q = [1]

→ true

MATCHING SINGLE NODES

either or both trees can be empty
each tree can hold up to a few thousand nodes
node values can be negative, zero, or positive
shape must match exactly — a missing child on one side is a mismatch

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Two trees match only if their roots match AND both pairs of children match. What's a direct way to encode 'the whole shape' so two encodings can just be compared?

HINT 2 THE STRUCTURE

A preorder walk that writes down a null marker for every missing child pins down a tree's shape uniquely — two trees are identical exactly when that encoding is identical.

HINT 3 ONE STEP FROM THE ANSWER

You don't have to build the encoding at all: compare the two roots directly, and the moment one node's value or presence disagrees with the other, stop and report false right there.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE PAIRED WALKPATTERN · PAIRED RECURSIONp = [1, 2] · q = [1, null, 2]

STEP 1

Same shape AND same values, node for node. Compare root to root first: tree1's root is 1, tree2's root is 1 — match.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/same-tree.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

TIME O(N)SPACE O(H)PYTHON · RACE PACE · 9 LN

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def serialize(node):
            if not node:
                return [None]
            return [node.val] + serialize(node.left) + serialize(node.right)

        return serialize(p) == serialize(q)

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

TIME O(N)SPACE O(H)JAVA · RACE PACE · 14 LN

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return serialize(p).equals(serialize(q));
    }

    private List<Integer> serialize(TreeNode node) {
        List<Integer> out = new ArrayList<>();
        if (node == null) {
            out.add(null);
            return out;
        }
        out.add(node.val);
        out.addAll(serialize(node.left));
        out.addAll(serialize(node.right));
        return out;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 17 LN

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