Problem Explanation

What is a Height-Balanced Binary Tree?

A height-balanced binary tree is one where for every node, the heights of its left and right subtrees differ by at most 1.

Think of it like this.

Imagine you’re building a tree structure, and you want it to be “stable” - not too lopsided in any direction.

A balanced tree ensures that no branch is significantly longer than others.

Key concept: Height of a tree

  • Height = the longest path from that node to a left
  • Empty tree has height 0
  • Single node has height 1

Example 1:

[3, 9, 20, null, null, 15, 7] -> true

      3
     / \
    9   20
       /  \
      15   7

  • Node 3: left subtree height = 1, right subtree height = 2, diffrence = 1

  • Node 9: no children, so balanced.

  • Node 20: left subtree height = 1, right subtree height = 1, diffrence = 0

All nodes satisfy the balance condition, so return true.

Example 2 [1,2,2,3,3,null,null,4,4] -> false

        1
       / \
      2   2
     / \
    3   3
   / \
  4   4
  • Node 1: left subtree height = 3, right subtree height = 1, so diffrence is 2.
  • This violates the balance condition.

And then Example 3, Empty tree is considered balanced by definition.

My Solution.

func isBalanced(_ root: TreeNode?) -> Bool {
    return dfs(root).0  // Return just the boolean part
}

private func dfs(_ root: TreeNode?) -> (Bool, Int) {
    // Base case: empty tree is balanced with height 0
    guard let root = root else { return (true, 0) }
    
    // Get info from left and right subtrees
    let left = dfs(root.left)
    let right = dfs(root.right)
    
    // Current node is balanced if:
    // 1. Both subtrees are balanced AND
    // 2. Height difference is at most 1
    let balanced = (left.0 && right.0 && abs(left.1 - right.1) <= 1)
    
    // Return: (is this subtree balanced?, height of this subtree)
    return (balanced, 1 + max(left.1, right.1))
}

I try to avoid redundant calculations.