Balanced Binary Tree — LeetCode 110 Postorder Height with Early Exit

Problem Statement#

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is one in which the depth of the two subtrees of every node never differs by more than 1.

Constraints:

• Number of nodes is in the range [0, 5000].
• -10^4 <= Node.val <= 10^4.

Input:  root = [3,9,20,null,null,15,7]
Output: true

Input:  root = [1,2,2,3,3,null,null,4,4]
Output: false

Why This Problem Matters#

LeetCode 110 — Balanced Binary Tree is the canonical "naive vs. optimal" tree-DP question. The naive approach computes height(left) and height(right) at every node, giving O(n log n) for balanced trees and O(n^2) for skewed ones. The optimal version uses a single postorder DFS with an early-exit sentinel and runs in O(n).

Amazon, Meta, Google, and Microsoft ask this regularly, often as a follow-up to Maximum Depth. It tests whether the candidate can fold two return values (height + balanced flag) into one and reason about postorder.

This is also the gateway to AVL trees and self-balancing BSTs, so senior engineers at Google L5+ frequently see this with a follow-up about rebalancing rotations.

The Core Insight#

Combine the height computation and the balance check into one postorder DFS. Define a helper height(node) that returns:

• The actual height if the subtree is balanced.
• -1 (a sentinel) the moment any subtree is unbalanced.

Once any subtree returns -1, the parent immediately propagates -1 upward. The top call sees -1 iff the tree is unbalanced.

This pattern — return one value, encode an exception as a sentinel — is reused in many tree-DP problems and is the canonical interview trick for "linearise the work".

Visual Dry Run#

Tree [3,9,20,null,null,15,7]:

        3
       / \
      9  20
        /  \
       15   7

No subtree returned -1, so the tree is balanced.

Solution (Optimal)#

# Python — postorder DFS with -1 sentinel
class Solution:
    def isBalanced(self, root):
        def height(node):
            if not node: return 0
            L = height(node.left)
            if L == -1: return -1
            R = height(node.right)
            if R == -1: return -1
            if abs(L - R) > 1: return -1
            return 1 + max(L, R)
        return height(root) != -1

// JavaScript — same trick
var isBalanced = function(root) {
    const height = (node) => {
        if (!node) return 0;
        const L = height(node.left);
        if (L === -1) return -1;
        const R = height(node.right);
        if (R === -1) return -1;
        if (Math.abs(L - R) > 1) return -1;
        return 1 + Math.max(L, R);
    };
    return height(root) !== -1;
};

# Naive O(n^2) version — only here for contrast
class SolutionNaive:
    def height(self, n):
        if not n: return 0
        return 1 + max(self.height(n.left), self.height(n.right))
    def isBalanced(self, root):
        if not root: return True
        if abs(self.height(root.left) - self.height(root.right)) > 1: return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

Time: O(n) for the optimal single-pass version. The naive recomputes heights, costing O(n log n) for balanced and O(n^2) for skewed. Space: O(h) recursion stack.

Common Mistakes#

• Using the naive approach and not noticing the O(n^2) blow-up when interviewer asks for complexity.
• Forgetting to short-circuit when L == -1 — wastes work and may overflow the stack.
• Computing diff using subtraction without abs, missing the case where right is taller.
• Returning True for an empty tree but 0 height — pick a consistent convention (empty = height 0, balanced = true).

Interview Tips#

• Code the naive solution first only if asked, then immediately propose the O(n) optimisation.
• The phrase "postorder DFS with sentinel" tells the interviewer you know the pattern.
• Define "height of empty tree = 0" before you write code.
• For a tougher signal, compute and return the actual height alongside the boolean using a tuple.

Follow-up Questions#

• Diameter of Binary Tree (LC 543)? Same shape — postorder height while updating a global max diameter.
• Convert Sorted Array to BST (LC 108)? Always pick the midpoint to keep tree balanced.
• Self-balancing AVL? Apply rotations on each insertion to maintain |L - R| <= 1.
• Average height vs. max height? This problem is about max-difference bounds, not averages.
• Iterative version? Possible with explicit stack of (node, returning?) frames.

Key Takeaways#

• LeetCode 110 Balanced Binary Tree runs in O(n) time and O(h) space with the postorder sentinel trick.
• Naive recomputation is O(n log n) for balanced and O(n^2) for skewed — interviewers expect you to optimize.
• The pattern is postorder DFS returning height, with -1 as the unbalanced sentinel.
• Asked at Amazon, Meta, Google, Microsoft, Apple as a follow-up to Maximum Depth.
• Foundation for Diameter of Binary Tree (LC 543), Maximum Path Sum (LC 124), and AVL trees.
• Empty tree is balanced with height 0 — agree on the convention upfront.
• Short-circuit on the first imbalance to keep the recursion linear.