Balanced Binary Tree - Solution & Explanation

Problem Overview: You are given the root of a binary tree and must determine whether it is height-balanced. A binary tree is balanced when the height difference between the left and right subtree of every node is at most one.

Approach 1: Recursive Height Calculation (O(n^2) time, O(h) space)

This straightforward solution computes the height of the left and right subtree for every node, then checks whether the difference exceeds one. Use a recursive height(node) function that returns 1 + max(leftHeight, rightHeight). During traversal, repeatedly call this function while verifying the balance condition. The drawback is repeated work: the height of the same subtree may be recomputed multiple times. In the worst case (a skewed tree), this leads to O(n^2) time while the recursion stack uses O(h) space where h is the tree height.

Approach 2: Optimized Recursive Approach (O(n) time, O(h) space)

This method combines balance checking and height calculation in a single DFS traversal. Instead of computing subtree heights separately, the recursive function returns the height of the subtree while also detecting imbalance early. If a subtree is already unbalanced, return a sentinel value such as -1. Each parent node checks whether either child returned -1 or whether the height difference exceeds one. If so, propagate -1 upward. Otherwise return the computed height. Because each node is visited exactly once, the algorithm runs in O(n) time with O(h) recursion stack space.

The solution relies on a depth-first traversal pattern commonly used in tree problems. Specifically, it performs a post-order DFS so the algorithm processes child subtrees before evaluating the parent node. This pattern appears frequently in depth-first search problems involving structural checks or subtree properties.

Balanced tree checks are a fundamental concept in binary tree algorithms because many data structures (AVL trees, Red-Black trees) rely on height balance to maintain efficient operations. Practicing this problem helps build intuition for computing subtree properties during traversal.

Recommended for interviews: The optimized recursive approach is the expected solution. It demonstrates that you can avoid redundant computations by combining height calculation with the balance check in a single DFS. Mentioning the naive O(n^2) approach first shows you understand the baseline, while implementing the O(n) solution proves you can optimize recursive tree algorithms.