Skip to content

080 — Same Tree

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

80 — Same Tree

LeetCode 100 · Easy. Given the roots of two binary trees p and q, check whether they are structurally identical and have identical node values at every corresponding position.

🍽️ Intuition

Imagine comparing two family trees to see if they're the exact same shape with the exact same names in every seat. You could photograph both trees completely, laying out every name in a fixed order, and then compare the two photographs side by side — but the moment you spot a single mismatch, there's no reason to keep comparing the rest of the photograph. It's faster to walk both trees together, node by node, in lockstep, and stop the instant something doesn't line up.

🚩 Pattern-Recognition Cue

"Are these two trees identical" / "same structure and same values" signals a simultaneous recursive descent — walk both trees together rather than each one separately, comparing the current pair of nodes before recursing into the current pair of left children and the current pair of right children.

🐢 Brute Force

Serialize each tree completely into an array (using a null marker so structure is preserved), then compare the two finished arrays for equality. This never looks at both trees together — it fully builds each serialization first, so it can't stop early even if the trees diverge on their very first node.

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val }
}

func serialize(_ node: TreeNode?, _ result: inout [Int?]) {
    guard let node = node else {
        result.append(nil)
        return
    }
    result.append(node.val)
    serialize(node.left, &result)
    serialize(node.right, &result)
}

func isSameTreeBruteForce(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
    var pSerialized: [Int?] = []
    var qSerialized: [Int?] = []
    serialize(p, &pSerialized)
    serialize(q, &qSerialized)

    guard pSerialized.count == qSerialized.count else { return false }
    for i in 0..<pSerialized.count {
        if pSerialized[i] != qSerialized[i] { return false }
    }
    return true
}

// smoke test
let p1 = TreeNode(1); p1.left = TreeNode(2); p1.right = TreeNode(3)
let q1 = TreeNode(1); q1.left = TreeNode(2); q1.right = TreeNode(3)
print(isSameTreeBruteForce(p1, q1))   // true

let p2 = TreeNode(1); p2.left = TreeNode(2)
let q2 = TreeNode(1); q2.right = TreeNode(2)
print(isSameTreeBruteForce(p2, q2))   // false — same values, different shape

Big-O: O(n) time — both trees are fully serialized regardless of where they might diverge, plus a linear array comparison. O(n) extra space for the two serialized arrays, held in memory simultaneously.

🚀 Optimal

Recurse on both trees at once. Compare the current pair of nodes; if they match, recurse into the left pair and the right pair. Return false the instant any mismatch is found, anywhere in the recursion.

func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
    if p == nil && q == nil { return true }
    guard let p = p, let q = q else { return false }   // exactly one is nil
    if p.val != q.val { return false }

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

// smoke test: same trees as above
let p3 = TreeNode(1); p3.left = TreeNode(2); p3.right = TreeNode(3)
let q3 = TreeNode(1); q3.left = TreeNode(2); q3.right = TreeNode(3)
print(isSameTree(p3, q3))   // true

let p4 = TreeNode(1); p4.left = TreeNode(2)
let q4 = TreeNode(1); q4.right = TreeNode(2)
print(isSameTree(p4, q4))   // false — as soon as p4.left (2) vs q4.left (nil) is compared, we bail

print(isSameTree(nil, nil))   // true — two empty trees are trivially identical

Big-O: O(n) time worst case (identical trees force a full walk), but far better in practice on divergent trees since it stops the instant a mismatch appears. O(h) extra space for the recursion stack, vs. the brute force's O(n) for two full serializations.

🔑 The Key Insight

The brute force can't short-circuit because it commits to fully describing each tree in isolation before it ever compares anything — by the time a mismatch would matter, both full serializations already exist. Walking both trees together means every recursive call has both current nodes in hand, so a mismatch is detectable — and returnable — the moment it's found, without finishing either tree. That's the general lesson: compare two structures incrementally, in lockstep, rather than fully describing each one and diffing the descriptions afterward.

🔗 Related Chapters

  • Binary Trees — the structure being compared.
  • DFS and Backtracking — the simultaneous recursive descent, short-circuiting on the first mismatch.
  • Subtree of Another Tree — reuses this exact same-tree comparison at every node of a larger tree to check for a matching subtree.

🧸 Memory Sentence

Same Tree is walking two trees side by side, hand in hand — the instant one hand finds something the other doesn't, you already know they're not the same.

✅ Check Your Understanding

Trace the optimal algorithm on p4 = 1 -> left(2) versus q4 = 1 -> right(2). At exactly which recursive call does it return false, and why does the brute force's full-serialization approach have to do strictly more work to reach the same answer?

⬅️ Previous: Balanced Binary Tree · Next: Subtree of Another Tree ➡️

Clone this wiki locally