One of the most common binary tree interview questions is Balanced Binary Tree. Although the problem is straightforward, it tests an important interview skill: combining multiple pieces of information during a single DFS traversal.

Let's break down the problem and gradually improve the solution.

---

Problem

Given the root of a binary tree, determine whether it is height-balanced.

A binary tree is considered balanced if, for every node, the height difference between its left and right subtree is at most one.

For example:

    1
   / \
  2   3
     /
    4

This tree is balanced because every node satisfies the height condition.

However,

      1
     / \
    2   3
       /
      4
     /
    5

is not balanced because the subtree rooted at 3 has a height difference greater than one.

---

Observation

To determine whether a node is balanced, we need two pieces of information from its children:

• The height of the left subtree
• The height of the right subtree

Once we know both heights, we simply check

abs(left_height - right_height) <= 1

The challenge is efficiently obtaining these heights for every node.

This immediately suggests post-order DFS, because a node cannot determine whether it is balanced until both of its children have already been processed.

---

Solution 1 — Global Boolean

The simplest approach is to compute the height of every subtree while storing a global boolean indicating whether we've found an imbalance.

class Solution:
    def isBalanced(self, root):
        self.res = True

        def dfs(node):
            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)

            if abs(left - right) > 1:
                self.res = False

            return 1 + max(left, right)

        dfs(root)
        return self.res

How it works

For every node:

1. Compute the left height.
2. Compute the right height.
3. Check whether their difference exceeds one.
4. Return the current height.

The recursion naturally processes the tree from the bottom upward.

Complexity

• Time: O(n)
• Space: O(h)

where h is the height of the tree.

---

Solution 2 — Early Exit with a Sentinel Value

We can improve the previous solution slightly.

Instead of visiting the entire tree after we've already discovered it isn't balanced, we can immediately propagate a special value upward.

A convenient sentinel is -1, since tree heights are never negative.

class Solution:
    def isBalanced(self, root):
        def dfs(node):
            if not node:
                return 0

            left = dfs(node.left)
            if left == -1:
                return -1

            right = dfs(node.right)
            if right == -1:
                return -1

            if abs(left - right) > 1:
                return -1

            return 1 + max(left, right)

        return dfs(root) != -1

Why this is better

Once an imbalance is detected, we stop doing unnecessary work higher up the tree.

Instead of calculating more heights, every recursive call simply returns -1.

This makes the solution cleaner and is often the version interviewers expect.

Complexity

• Time: O(n)
• Space: O(h)

Although the worst-case complexity is still O(n), many trees terminate earlier in practice.

---

Solution 3 — Returning Multiple Values

Another elegant approach is returning everything we need from each DFS call.

Instead of using a global variable or a sentinel value, each recursive call returns:

(isBalanced, height)

class Solution:
    def isBalanced(self, root):
        def dfs(node):
            if not node:
                return (True, 0)

            left = dfs(node.left)
            right = dfs(node.right)

            balanced = (
                left[0]
                and right[0]
                and abs(left[1] - right[1]) <= 1
            )

            return (balanced, 1 + max(left[1], right[1]))

        return dfs(root)[0]

Why this works

Every recursive call provides exactly the information its parent needs:

• whether the subtree is balanced
• the subtree height

The parent simply combines these values to determine its own result.

Many interviewers like this approach because it avoids global state and keeps all information flowing through the recursion naturally.

---

Why Post-Order DFS?

Notice that we must process children before their parent.

At each node we need both subtree heights before making a decision.

That makes this a classic post-order traversal.

Left
Right
Current Node

Trying to use pre-order traversal would require repeatedly recalculating subtree heights, leading to a much slower solution.

---

Common Interview Mistake

Many candidates first write something like this:

height(node.left)
height(node.right)

inside every recursive call.

Unfortunately, this recalculates subtree heights repeatedly.

isBalanced(root)
    ├── height(left)
    ├── height(right)
    ├── isBalanced(left)
    │      ├── height(...)
    │      ├── height(...)

The same subtree heights are computed over and over again.

This results in O(n²) time complexity in the worst case.

The optimal approach computes each subtree height once during a single DFS traversal.

---

Which Solution Should You Use?

Solution	Pros	Cons
Global boolean	Very easy to understand	Continues traversing after finding an imbalance
Sentinel (-1)	Stops unnecessary work early and is concise	Slightly less intuitive for beginners
Return (balanced, height)	Clean, functional style with no global state	Returns a tuple on every recursive call

---

Interview Takeaways

Whenever a tree problem asks you to determine something about a node based on information from its children, think post-order DFS.

For this problem, every node needs:

• left subtree height
• right subtree height
• whether both subtrees are already balanced

Computing all of this in a single traversal gives the optimal O(n) solution.

The sentinel (-1) solution is probably the one you'll see most often in interviews, but all three approaches demonstrate the same core idea: combine height calculation and balance checking into one DFS.