Balanced Binary Tree

Difficulty: Easy Source: NeetCode

Problem

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

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

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

Constraints:

• The number of nodes in the tree is in the range [0, 5000]
• -100 <= Node.val <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

• Tree Height — Recursive computation of the longest path from a node to a leaf
• DFS Post-order — Computing results bottom-up
• Sentinel Values — Using -1 to signal an error/invalid state up the call stack

1. Naive Approach (Two Passes)

Intuition

The straightforward reading: for every node, check if abs(height(left) - height(right)) <= 1, then recurse on children. This is correct but slow — height is called repeatedly on the same nodes.

Algorithm

1. Define height(node) that returns the max depth of a subtree
2. Define is_balanced(node):
   • If null, return true
   • Check abs(height(left) - height(right)) <= 1
   • Recursively check both subtrees

Solution

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

def is_balanced_naive(root):
    def height(node):
        if not node:
            return 0
        return 1 + max(height(node.left), height(node.right))

    def check(node):
        if not node:
            return True
        left_h = height(node.left)
        right_h = height(node.right)
        if abs(left_h - right_h) > 1:
            return False
        return check(node.left) and check(node.right)

    return check(root)

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 9, 20, None, None, 15, 7])
print(is_balanced_naive(root1))  # True

root2 = build_tree([1, 2, 2, 3, 3, None, None, 4, 4])
print(is_balanced_naive(root2))  # False

root3 = build_tree([])
print(is_balanced_naive(root3))  # True

Complexity

• Time: O(n²) — height is called O(n) times, each taking O(n) in the worst case
• Space: O(h) — recursion depth

2. Optimal DFS (Single Pass)

Intuition

Instead of computing height separately, we combine the height computation with the balance check in one DFS pass. The function returns the height if the subtree is balanced, or -1 as a sentinel value to signal “this subtree is already unbalanced — stop early.”

Algorithm

1. Define dfs(node) returning height or -1 if unbalanced:
   • Null node returns height 0
   • Compute left and right heights
   • If either is -1, propagate -1 upward (early exit)
   • If abs(left - right) > 1, return -1
   • Otherwise return 1 + max(left, right)
2. Return dfs(root) != -1

Solution

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

def is_balanced(root):
    def dfs(node):
        if not node:
            return 0  # Height of empty subtree

        left_h = dfs(node.left)
        if left_h == -1:
            return -1  # Short-circuit: left is already unbalanced

        right_h = dfs(node.right)
        if right_h == -1:
            return -1  # Short-circuit: right is already unbalanced

        if abs(left_h - right_h) > 1:
            return -1  # This node violates balance

        return 1 + max(left_h, right_h)

    return dfs(root) != -1

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 9, 20, None, None, 15, 7])
print(is_balanced(root1))  # True

root2 = build_tree([1, 2, 2, 3, 3, None, None, 4, 4])
print(is_balanced(root2))  # False

root3 = build_tree([])
print(is_balanced(root3))  # True

root4 = build_tree([1, 2, 2, 3, None, None, 3, 4, None, None, 4])
print(is_balanced(root4))  # False

Complexity

• Time: O(n) — each node is visited exactly once
• Space: O(h) — recursion stack

Common Pitfalls

Checking only the root. A tree where the root’s children have heights 2 and 3 can still be unbalanced deeper down. The check must happen at every node.

Using -1 as both a valid return and a sentinel. Height is always >= 0 for existing nodes, so -1 is safe as a sentinel. If the problem involved negative values that could become heights, you’d need a different signal (like None or a named exception).