Skip to content

079 — Balanced Binary Tree

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

79 — Balanced Binary Tree

LeetCode 110 · Easy. Given the root of a binary tree, determine if it is height-balanced — for every node, the height difference between its left and right subtrees is at most 1.

🍽️ Intuition

Balance is a property that has to hold everywhere, not just at the top. A tree can look perfectly fine at the root — left and right heights matching exactly — while some node three levels down is wildly lopsided. So you need to check the balance condition at every single node, and the moment you find one violation anywhere in the tree, the whole tree is unbalanced, full stop — there's no point checking the rest.

🚩 Pattern-Recognition Cue

"Height-balanced" / "height difference at most 1, for every node" is the same "check something at every node using subtree heights" shape as Diameter of Binary Tree — which means it has the exact same O(n²)-trap-vs-O(n)-fix structure: naively recomputing height per node, or computing it once bottom-up and threading imbalance detection through the same pass.

🐢 Brute Force

For every node, separately recompute the height of its left and right subtrees from scratch, check the difference is at most 1, and recurse into both children to check the same condition there.

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

// recomputes height from scratch every time it's called
func height(_ node: TreeNode?) -> Int {
    guard let node = node else { return 0 }
    return 1 + max(height(node.left), height(node.right))
}

func isBalancedBruteForce(_ root: TreeNode?) -> Bool {
    guard let root = root else { return true }

    let leftHeight = height(root.left)
    let rightHeight = height(root.right)

    if abs(leftHeight - rightHeight) > 1 {
        return false
    }

    return isBalancedBruteForce(root.left) && isBalancedBruteForce(root.right)
}

// smoke test: balanced tree 3 -> (9, 20 -> (15, 7))
let bfBalanced = TreeNode(3)
bfBalanced.left = TreeNode(9)
bfBalanced.right = TreeNode(20)
bfBalanced.right?.left = TreeNode(15)
bfBalanced.right?.right = TreeNode(7)
print(isBalancedBruteForce(bfBalanced))   // true

// smoke test: unbalanced tree 1 -> (2 -> (3 -> (4)))  — a chain hanging off the left
let bfUnbalanced = TreeNode(1)
bfUnbalanced.left = TreeNode(2)
bfUnbalanced.left?.left = TreeNode(3)
bfUnbalanced.left?.left?.left = TreeNode(4)
print(isBalancedBruteForce(bfUnbalanced))   // false

Big-O: O(n²) time in the worst case — every node triggers two full-subtree height calls, giving the same 1 + 2 + ... + n blowup as Diameter of Binary Tree on a skewed input. O(h) extra space for the recursion stack.

🚀 Optimal

Do a single bottom-up DFS that returns each node's height — but the moment any subtree reports imbalance, short-circuit by returning a sentinel value (-1) upward instead of a real height, so no further work is wasted checking a tree that's already known to be unbalanced.

func isBalanced(_ root: TreeNode?) -> Bool {
    func checkHeight(_ node: TreeNode?) -> Int {
        guard let node = node else { return 0 }

        let leftHeight = checkHeight(node.left)
        if leftHeight == -1 { return -1 }   // left subtree already unbalanced — bail immediately

        let rightHeight = checkHeight(node.right)
        if rightHeight == -1 { return -1 }  // right subtree already unbalanced — bail immediately

        if abs(leftHeight - rightHeight) > 1 { return -1 }   // this node itself is unbalanced

        return 1 + max(leftHeight, rightHeight)
    }

    return checkHeight(root) != -1
}

// smoke test: same balanced and unbalanced trees as above
let balanced = TreeNode(3)
balanced.left = TreeNode(9)
balanced.right = TreeNode(20)
balanced.right?.left = TreeNode(15)
balanced.right?.right = TreeNode(7)
print(isBalanced(balanced))   // true

let unbalanced = TreeNode(1)
unbalanced.left = TreeNode(2)
unbalanced.left?.left = TreeNode(3)
unbalanced.left?.left?.left = TreeNode(4)
print(isBalanced(unbalanced))   // false

print(isBalanced(nil))   // true — an empty tree is trivially balanced

Big-O: O(n) time — each node's height is computed exactly once in the single bottom-up pass, and the -1 sentinel lets already-failed branches skip further comparison work. O(h) extra space for the recursion stack.

🔑 The Key Insight

-1 isn't just an error code here — it's an overloaded return value that lets a single function serve two purposes at once: "here's this subtree's real height" and "stop checking, we already know this tree is unbalanced." That overload is what collapses the brute force's separate "compute height" and "check balance at this node" passes into one traversal. Just like Diameter of Binary Tree, the trap is recomputing a subtree's height freshly at every node that needs it; the fix is computing each height exactly once, bottom-up, and piggybacking the balance check on the same return value.

🔗 Related Chapters

  • Binary Trees — the structure, and the notion of subtree height that balance depends on.
  • DFS and Backtracking — the single bottom-up pass with a sentinel-based early exit.
  • Diameter of Binary Tree — the same O(n²)-naive-height-recomputation-vs-O(n)-single-pass shape, solved with the same kind of post-order DFS.

🧸 Memory Sentence

Balanced Binary Tree is checking every node's left-vs-right height gap in one bottom-up sweep — and the instant one node fails, a -1 sentinel carries the bad news straight to the top without re-measuring anything.

✅ Check Your Understanding

Trace the optimal algorithm on the unbalanced tree 1 -> 2 -> 3 -> 4 (a left-only chain). At which node does checkHeight first return -1, and how does that -1 propagate back up through the remaining recursive calls to isBalanced's top-level check, without any of those outer calls doing further height arithmetic?

⬅️ Previous: Diameter of Binary Tree · Next: Same Tree ➡️

Clone this wiki locally