Balanced Binary Tree — Step-by-Step Visualization

Algorithm Pattern

Recursive Height Tracker

Key Idea

A tree is balanced if: (1) Its left subtree is balanced, (2) Its right subtree is balanced, and (3) The difference between the heights of the left and right subtrees is at most 1. We can combine these checks into a single recursive function that returns the height of the subtree if it's balanced, or -1 if it's not.

Step-by-Step Approach

1. Base Case: If `node` is null, its height is 0.
2. Recurse Left: Get the height of the left subtree. If it's -1, return -1.
3. Recurse Right: Get the height of the right subtree. If it's -1, return -1.
4. Balance Check: If `abs(left_height - right_height) > 1`, return -1 (unbalanced).
5. Return: `1 + max(left_height, right_height)` if balanced.

Common Gotchas

• Returning -1 is a clever way to propagate the 'unbalanced' state up the recursion stack without having to check every node multiple times.