Balanced Binary Tree

A reliable Balanced Binary Tree solution carries two facts upward from every subtree: its height and whether it is balanced.

What does “balanced” mean?

A binary tree is height-balanced when, for every node, the heights of its left and right subtrees differ by no more than one.

For a node to be balanced, all three conditions must hold:

1. Its left subtree is balanced.
2. Its right subtree is balanced.
3. The difference between the two child heights is at most 1.

abs(left_height - right_height) <= 1

The condition applies to every node, not just the root. Node values do not matter, so this is a structural binary-tree problem rather than a binary-search-tree problem.

We will use this height convention:

• An empty subtree has height 0.
• A leaf has height 1.
• A non-empty subtree has height 1 + max(left_height, right_height).

The empty tree is balanced, so an empty input must return True.

Recognize the bottom-up DFS pattern

At a node, you cannot check its balance until you know the heights of both children. You also need to know whether those child subtrees are already invalid.

That dependency determines the traversal order:

1. Solve the left subtree.
2. Solve the right subtree.
3. Use both results to solve the current node.

This is postorder depth-first search. Information moves upward from the leaves, like measurements moving through a reporting chain.

A tempting approach is to calculate the height of each subtree separately:

For every node:
    calculate the left subtree height
    calculate the right subtree height
    check the difference

That repeats work. Consider a one-sided chain of n nodes. If you calculate the height independently at every node, the root walks through roughly n nodes, its child walks through roughly n - 1, the next node walks through roughly n - 2, and so on. The total work is:

n + (n - 1) + (n - 2) + ... + 1 = O(n²)

The bottom-up solution measures each subtree once. A node computes its height, checks its own balance, and returns that summary to its parent. No ancestor needs to walk through the same descendants again.

The helper contract is:

dfs(node) -> (whether the subtree is balanced, its height)

That contract is the core of the solution. The code only transports the information.

Derive the recurrence

Start with the missing-node case:

dfs(None) -> (True, 0)

An empty subtree contains no node that can violate the balance condition, and its height is 0.

For a non-empty node, recursively collect both child summaries:

left_balanced, left_height = dfs(node.left)
right_balanced, right_height = dfs(node.right)

The current subtree is balanced exactly when both child subtrees are balanced and the current height difference is allowed:

current_balanced =
    left_balanced
    and right_balanced
    and abs(left_height - right_height) <= 1

Its height is:

current_height = 1 + max(left_height, right_height)

The resulting invariant is:

Every dfs(node) call returns the exact height of node’s subtree, and its boolean reports whether every node in that subtree satisfies the balance condition.

The height is the measurement the parent needs. The boolean carries the validity of all deeper nodes. Return both, and the parent has everything required to continue.

Why this solution is correct

We can prove the helper contract by induction on the subtree.

Base case

For node = None, the helper returns (True, 0).

The empty subtree is balanced because it contains no violating node, and its height is 0 by definition. The contract holds.

Inductive step

Assume the helper correctly reports the balance and height of the left and right subtrees.

There are two cases.

One child subtree is unbalanced.

The current subtree contains that invalid subtree, so it cannot be balanced. Returning False is correct.

Both child subtrees are balanced.

By the induction assumption, left_height and right_height are their exact heights. The current node satisfies the balance condition precisely when their difference is at most one.

• If abs(left_height - right_height) > 1, the current subtree is unbalanced.
• Otherwise, the current node is balanced, and its exact height is 1 + max(left_height, right_height).

Therefore, the helper returns the correct result for the current subtree. At the root, that result describes the entire tree.

Dry run: the state moves upward

Consider this tree:

        1
       / \
      2   3
     /     \
    4       6
   /
  5

The subtree rooted at 2 is internally unbalanced, but the root’s immediate subtree heights differ by only one.

Process the leaves first:

Subtree	Left height	Right height	Result	Returned height
5	0	0	balanced	1
4	1	0	balanced	2
6	0	0	balanced	1
3	0	1	balanced	2

Now inspect node 2:

Subtree	Left height	Right height	Result	Returned height
2	2	0	unbalanced	3

Finally, inspect the root:

• Left subtree height: 3
• Right subtree height: 2
• Root difference: 1

The root passes its local height check. The entire tree is still unbalanced because node 2 failed.

This is why root-only checking is insufficient: a node can look locally valid while a lower node violates the universal condition.

For comparison, this tree is balanced:

        1
       / \
      2   3
     /
    4

At the root, the child heights are 2 and 1, so the difference is exactly 1. Node 2 also has child heights 1 and 0, so every node satisfies the condition.

Two base cases should become automatic:

• Empty tree: (True, 0), so the public method returns True.
• Single-node tree: both child heights are 0, so the node has height 1 and is balanced.

Implement the Balanced Binary Tree solution in Python

The platform provides TreeNode; only its left and right fields matter here. The node value is never inspected.

from typing import Optional


class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode]) -> tuple[bool, int]:
            if node is None:
                return True, 0

            left_balanced, left_height = dfs(node.left)
            right_balanced, right_height = dfs(node.right)

            balanced = (
                left_balanced
                and right_balanced
                and abs(left_height - right_height) <= 1
            )

            height = 1 + max(left_height, right_height)
            return balanced, height

        balanced, _ = dfs(root)
        return balanced

Read the implementation through the helper contract:

• None returns a balanced empty subtree with height 0.
• Each recursive call returns the two facts needed by its parent.
• balanced checks both child results and the current height difference.
• height computes the summary that the parent will need.
• The public method returns only the boolean because callers do not need the root’s height.

The code computes the height even when one child is already unbalanced. That keeps the tuple contract uniform and easy to inspect. You could add early exits, but that is an implementation refinement rather than a different algorithm. In an interview, I would start with the complete tuple version: each returned value has an obvious meaning, and the correctness argument maps directly to the code.

Complexity and edge cases

Let n be the number of nodes and h be the tree height.

Time complexity

Each node is processed once:

• Its children are solved once.
• Its balance condition is checked once.
• Its height is calculated once.

The time complexity is:

O(n)

Space complexity

The recursive call stack can contain one frame for each tree level:

O(h)

For a shallow tree, this is small. For a completely skewed tree, h can be proportional to n, so the worst-case auxiliary space is O(n).

Important edge cases

Case	Expected result	Reason
Empty tree	True	No node violates the condition
One node	True	Both child heights are 0
Two-node chain	True	The parent’s height difference is 1
Three-node one-sided chain	False	The root’s difference is 2
Imbalanced subtree below a balanced-looking root	False	Every node must be balanced
Negative or duplicate values	Shape-dependent	Values do not affect balance

Common implementation failures are predictable:

1. Checking only the root
   This misses invalid subtrees lower in the tree.

2. Recomputing height independently at every node
   This repeats subtree work and can become quadratic on a skewed tree.

3. Applying binary-search-tree rules
   This problem does not require sorted values or any ordering relationship.

4. Mixing height conventions
   If an empty subtree has height 0, a leaf must have height 1.

5. Rejecting a difference of exactly one
   A difference of 1 is allowed. The condition fails only when the difference is greater than 1.

Before submitting, trace the helper on two tiny structures: an empty tree and a one-sided chain of three nodes. If your base case, height convention, and > 1 comparison are correct, those traces expose most beginner mistakes quickly.

The transferable pattern

When a tree condition depends on properties of both child subtrees, use a postorder DFS that returns those properties upward.

For this problem, the state is:

balance validity + subtree height

For another tree problem, the state might be a subtree sum, maximum path value, search bound, or matching status. The reasoning move stays the same:

1. Identify what the parent needs from each child.
2. Make those facts the helper’s return contract.
3. Solve both children before evaluating the current node.
4. Propagate failure when the subtree can no longer satisfy the contract.

Write the contract first. Then write the recursion. The implementation becomes smaller, and the explanation becomes something you can prove rather than something you hope passes the examples.