Same Tree

easyTests passed 2026-11-11v1.0.0
TC: O(min(P, Q))|SC: O(min(Hp, Hq))
TreesOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Base cases first: both null => `True`; one null => `False`; values differ => `False`. Otherwise recursively verify left and right child equality.

2. Complexity Bounds & Proof

Mismatch terminates immediately; full match inspects every shared node once.

3. Minimal Idiomatic Code

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

4. Failure Modes & Interview Follow-ups

Pitfalls:- Trying to validate via a single traversal list (e.g. inorder only) fails without null markers.
Follow-ups:- Symmetric Tree checks `isMirror(root.left, root.right)` with `left.left vs right.right` and `left.right vs right.left`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Subtree of Another Tree (O(S * T))Invert Binary Tree (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.