LeetCode 110 - Balanced Binary Tree

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to determine whether a given binary tree is height-balanced.

A binary tree is considered height-balanced if, for every node in the tree, the height difference between its left and right subtrees is at most 1.

In simpler terms, the tree should not be heavily skewed to one side at any point. Even if the root itself appears balanced, the tree is not balanced if any subtree violates the balance condition.

The input is the root node of a binary tree. The tree is represented in level-order form in the examples, where null indicates a missing child node.

For example:

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

Represents:

This tree is balanced because every node has left and right subtree heights that differ by at most 1.

The expected output is a boolean:

true if the tree is height-balanced
false if any node violates the balance condition

The constraints tell us that the number of nodes is between 0 and 5000.

This is relatively small, but still large enough that inefficient repeated work can become problematic. A quadratic time solution may pass for some cases, but we should still aim for a linear solution.

The node values themselves are irrelevant to the balance condition. Only the shape of the tree matters.

Several edge cases are important to consider upfront.

An empty tree should return true, because a tree with no nodes is trivially balanced.

A tree with only one node is balanced since both subtrees have height 0.

Highly skewed trees, such as a linked-list shaped tree, can easily violate the balance condition and expose inefficiencies in naive solutions.

Another subtle case is when the root appears balanced, but a deeper subtree is not. A correct solution must verify balance recursively for every node, not just the root.

Approaches

Brute Force Approach

A straightforward approach is to check whether every node satisfies the balance condition independently.

For each node:

Compute the height of the left subtree.
Compute the height of the right subtree.
Check whether the height difference exceeds 1.
Recursively repeat this process for the left and right children.

The main issue is that height calculations are repeatedly recomputed.

Consider a skewed tree:

To check node 1, we compute the height of node 2.

Then, while checking node 2, we compute the height of node 3 again.

Then node 3 recomputes node 4, and so on.

This repeated traversal creates a large amount of duplicate work.

The approach is correct because it explicitly verifies the balance condition at every node. However, it becomes inefficient since subtree heights are recalculated many times.

Optimal Approach, Bottom-Up DFS

The key observation is that balance checking and height computation can happen simultaneously.

Instead of repeatedly computing heights, we can perform a postorder depth-first traversal, where we process child subtrees before their parent.

For each node:

First determine whether the left subtree is balanced and obtain its height.
Then determine whether the right subtree is balanced and obtain its height.
If either subtree is already unbalanced, propagate failure immediately.
If the current node violates the height difference rule, mark it unbalanced.
Otherwise, return the node's height.

A useful optimization is to return a special sentinel value such as -1 to indicate that a subtree is unbalanced.

This allows us to stop unnecessary work early.

Instead of returning only height:

height(node)

We return:

-1  -> subtree is unbalanced
>=0 -> subtree height

This transforms the problem into a single traversal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly recalculates subtree heights
Optimal	O(n)	O(h)	Single DFS traversal computes height and balance together

Here, n is the number of nodes and h is the tree height.

Algorithm Walkthrough

Optimal Bottom-Up DFS Algorithm

Define a helper function that computes subtree height.

Instead of returning only height, this helper returns:

-1 if the subtree is unbalanced
a non-negative integer representing height otherwise

This design allows us to combine balance checking with height computation. 2. Handle the base case.

If the current node is None (or nil in Go), return height 0.

An empty subtree is balanced and contributes no height. 3. Recursively compute the left subtree height.

Call the helper on the left child.

If it returns -1, we immediately propagate -1 upward because the subtree is already unbalanced. 4. Recursively compute the right subtree height.

Repeat the same process for the right child.

Again, if -1 is returned, stop early and propagate failure. 5. Check the balance condition at the current node.

Compute:

abs(leftHeight - rightHeight)

If the difference exceeds 1, return -1.

This indicates the current subtree is not balanced. 6. Compute and return the subtree height.

If the node is balanced, return:

1 + max(leftHeight, rightHeight)

The +1 accounts for the current node. 7. Evaluate the final result.

Call the helper on the root.

If the result is -1, return False.

Otherwise, return True.

Why it works

The algorithm works because every node is evaluated only after its children have already been processed.

At any node, we already know:

whether the left subtree is balanced
whether the right subtree is balanced
the heights of both subtrees

This information is sufficient to determine whether the current node is balanced.

The invariant is that the helper function always returns either a valid subtree height for balanced trees or -1 for unbalanced trees. Since this invariant holds for leaf nodes and propagates upward correctly, the final result at the root is guaranteed to be correct.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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

            left_height = height(node.left)
            if left_height == -1:
                return -1

            right_height = height(node.right)
            if right_height == -1:
                return -1

            if abs(left_height - right_height) > 1:
                return -1

            return 1 + max(left_height, right_height)

        return height(root) != -1

The implementation follows a bottom-up recursive strategy.

The nested height() helper function performs the real work. It recursively computes subtree heights while also checking balance.

The first condition handles the base case. A None node contributes height 0.

The recursive calls process the left and right children first. This is a postorder traversal because children are evaluated before their parent.

If either subtree returns -1, the function immediately propagates failure upward. This prevents unnecessary computation once imbalance has already been detected.

The line:

if abs(left_height - right_height) > 1:

checks the core balance requirement.

If the node is balanced, we return:

1 + max(left_height, right_height)

which correctly computes subtree height.

Finally, the main function checks whether the root result is -1. If not, the tree is balanced.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    var height func(node *TreeNode) int

    height = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftHeight := height(node.Left)
        if leftHeight == -1 {
            return -1
        }

        rightHeight := height(node.Right)
        if rightHeight == -1 {
            return -1
        }

        difference := leftHeight - rightHeight
        if difference < 0 {
            difference = -difference
        }

        if difference > 1 {
            return -1
        }

        if leftHeight > rightHeight {
            return leftHeight + 1
        }

        return rightHeight + 1
    }

    return height(root) != -1
}

The Go implementation follows the exact same logic as the Python version.

Instead of nested functions being freely declared like Python, Go uses a function variable:

var height func(node *TreeNode) int

This allows recursion inside an anonymous function.

Go uses nil instead of None for empty nodes.

Since Go does not have a built-in integer absolute value function for integers without importing packages, the absolute difference is computed manually:

difference := leftHeight - rightHeight
if difference < 0 {
    difference = -difference
}

The logic otherwise remains identical. The helper returns -1 for imbalance and subtree height for balanced cases.

Worked Examples

Example 1

Input:

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

Tree:

Traversal proceeds bottom-up.

Node	Left Height	Right Height	Balanced?	Returned Height
9	0	0	Yes	1
15	0	0	Yes	1
7	0	0	Yes	1
20	1	1	Yes	2
3	1	2	Yes	3

Final result:

height(root) = 3

Since the result is not -1, output is:

true

Example 2

Input:

[1,2,2,3,3,null,null,4,4]

Tree:

Bottom-up traversal:

Node	Left Height	Right Height	Balanced?	Returned Height
4	0	0	Yes	1
4	0	0	Yes	1
3	1	1	Yes	2
3	0	0	Yes	1
2	2	1	Yes	3
1	3	1	No	-1

At the root:

abs(3 - 1) = 2

This exceeds 1, so the tree is unbalanced.

Output:

false

Example 3

Input:

[]

The tree is empty.

Node	Result
None	Height = 0

Since an empty tree is balanced:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once
Space	O(h)	Recursive call stack depends on tree height

Here, n is the number of nodes and h is the height of the tree.

The algorithm achieves linear time because every node performs constant work exactly once.

The space complexity comes from recursion. In a balanced tree, the recursion depth is approximately O(log n). In the worst case, such as a skewed tree, recursion depth becomes O(n).

Test Cases

# Helper TreeNode class for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1: balanced tree
root1 = TreeNode(
    3,
    TreeNode(9),
    TreeNode(20, TreeNode(15), TreeNode(7))
)
assert solution.isBalanced(root1) is True  # standard balanced tree

# Example 2: unbalanced tree
root2 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(3, TreeNode(4), TreeNode(4)),
        TreeNode(3)
    ),
    TreeNode(2)
)
assert solution.isBalanced(root2) is False  # imbalance at root

# Example 3: empty tree
assert solution.isBalanced(None) is True  # empty tree is balanced

# Single node tree
root4 = TreeNode(1)
assert solution.isBalanced(root4) is True  # minimal non-empty tree

# Perfectly balanced tree
root5 = TreeNode(
    1,
    TreeNode(2),
    TreeNode(3)
)
assert solution.isBalanced(root5) is True  # equal subtree heights

# Left-skewed tree
root6 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(
            3
        )
    )
)
assert solution.isBalanced(root6) is False  # excessive left depth

# Right-skewed tree
root7 = TreeNode(
    1,
    None,
    TreeNode(
        2,
        None,
        TreeNode(3)
    )
)
assert solution.isBalanced(root7) is False  # excessive right depth

# Deep imbalance not at root
root8 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(
            3,
            TreeNode(4)
        )
    ),
    TreeNode(2)
)
assert solution.isBalanced(root8) is False  # subtree imbalance

# Difference exactly 1
root9 = TreeNode(
    1,
    TreeNode(2, TreeNode(3)),
    TreeNode(2)
)
assert solution.isBalanced(root9) is True  # boundary balance condition

Test	Why
Example 1 balanced tree	Validates standard balanced input
Example 2 unbalanced tree	Validates imbalance detection
Empty tree	Confirms base case handling
Single node	Ensures minimal tree works
Perfectly balanced tree	Verifies equal heights
Left-skewed tree	Tests excessive left depth
Right-skewed tree	Tests excessive right depth
Deep imbalance	Ensures all subtrees are checked
Difference exactly 1	Validates boundary condition

Edge Cases

Empty Tree

An empty tree is a common edge case that can easily be mishandled if recursion is not designed properly.

Since there are no nodes, the tree is trivially balanced. The implementation correctly handles this through:

if node is None:
    return 0

This ensures the algorithm immediately returns a valid height.

Highly Skewed Tree

A tree shaped like a linked list is another important case.

Example:

A naive implementation may repeatedly recompute heights, causing poor performance.

The bottom-up approach avoids repeated work and correctly detects imbalance when subtree height difference exceeds 1.

Imbalance Deep in a Subtree

Sometimes the root itself appears balanced, but imbalance exists lower in the tree.

Example:

A flawed solution that checks only the root would incorrectly return true.

This implementation recursively validates every subtree and propagates -1 upward, ensuring deep imbalances are never missed.