Height Balanced Binary Tree

Tags

Height Balanced Binary Tree

Category

Binary Trees

Difficulty

Medium

Problem Statement

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is one in which the heights of the left and right subtrees of every node differ by at most 1.

Intuition

We can check the balance condition at every node by computing subtree heights bottom-up. If at any node the height difference between left and right exceeds 1, the tree is not balanced. By combining the height computation with the balance check in a single recursive traversal, we avoid redundant work.

Approach

  1. Define a recursive helper that returns both the height of the subtree and whether it is balanced.
  2. Base case: a null node has height 0 (or -1, depending on convention) and is balanced.
  3. Recursive step: a. Recursively compute the height and balance status of the left subtree. b. Recursively compute the height and balance status of the right subtree. c. The current node is balanced if: both subtrees are balanced AND abs(leftHeight - rightHeight) <= 1. d. The current height is 1 + max(leftHeight, rightHeight).
  4. Return whether the root is balanced.

Pseudocode

function isBalanced(root):
    return checkBalance(root).isBalanced

function checkBalance(node):
    if node is null:
        return { height: 0, isBalanced: true }

    left = checkBalance(node.left)
    right = checkBalance(node.right)

    isCurrentBalanced = left.isBalanced
                        and right.isBalanced
                        and abs(left.height - right.height) <= 1

    height = 1 + max(left.height, right.height)

    return { height: height, isBalanced: isCurrentBalanced }

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Each node is visited exactly once.
  • Space: O(h) where h is the height of the tree, for the recursion stack. Worst case O(n) for a skewed tree, O(log n) for a balanced tree.

Key Insights

  • A naive approach that computes height separately for each node would be O(n^2). Combining height and balance in one pass gives O(n).
  • Early termination is possible: if a subtree is found to be unbalanced, we can propagate this upward without further computation. This can be done by returning a sentinel height (e.g., -1) to indicate imbalance.
  • The balance condition must hold for every node, not just the root. A tree with a balanced root but an unbalanced subtree is not balanced.

Edge Cases

  • Empty tree (null root): considered balanced, return true.
  • Single node: balanced with height 1.
  • Perfectly balanced tree: all leaves at the same or adjacent levels.
  • Skewed tree (linked list): not balanced once height exceeds 1.
  • Tree balanced at the root but unbalanced deeper: must check all nodes.

Linked mentions