L15. Check for Balanced Binary Tree

A comprehensive study note on validating whether a binary tree is height-balanced, transitioning from an inefficient $O(N^2)$ brute-force approach to an optimized $O(N)$ single-pass solution using clever recursive state encoding.

1. Problem Statement & Definition of a Balanced Binary Tree

In data structures and algorithms, determining tree balance is a fundamental validation problem. A Balanced Binary Tree (often referred to in libraries like AVL trees) is defined as a binary tree in which the height difference between the left subtree and the right subtree of every single node is less than or equal to 1.

Formally, for every node $N$ in the tree, the following condition must hold true:

If even a single node violates this rule, the entire binary tree is classified as unbalanced.

2. Core Mental Model & Visualizing Balance

Real-Life Analogy

Imagine balancing a mobile hanging from the ceiling or an organizational hierarchy where every manager's left and right departments must remain roughly equal in depth. If one side grows excessively deep while the other remains shallow, the structure tilts dangerously, losing its equilibrium.

Visualizing Balanced vs. Unbalanced Trees

Example 1: Balanced Binary Tree

         3
       /   \
      9     20
           /  \
          15   7

• At Node 20: Left height = 1 (node 15), Right height = 1 (node 7). Difference = |1 - 1| = 0 $\le 1$ (Balanced).
• At Node 3: Left height = 1 (node 9), Right height = 2 (sub-branch 20 -> 15). Difference = |1 - 2| = 1 $\le 1$ (Balanced).
• Result: The tree is balanced.

Example 2: Unbalanced Binary Tree

         1
        /
       2
      /
     3
    /
   4
    \
     5

• At Node 1: Left subtree depth is 3 (nodes 2 -> 3 -> 4), while the right subtree depth is 0. Difference = |3 - 0| = 3, which is $> 1$.
• Result: The tree is not balanced.

3. The Naive Approach ($O(N^2)$) and Why It Fails

The Intuitive Strategy

The most straightforward way to solve this problem is to visit every node individually. For each node encountered during traversal:

1. Calculate the height of its left subtree.
2. Calculate the height of its right subtree.
3. Check if the absolute difference exceeds 1. If it does, immediately return false.
4. Recursively repeat this check for the left and right children.

Pseudo-Code for Naive Approach

function isBalancedNaive(node: TreeNode | null): boolean {
    if (node === null) return true;

    const leftHeight = getHeight(node.left);
    const rightHeight = getHeight(node.right);

    if (Math.abs(leftHeight - rightHeight) > 1) {
        return false;
    }

    return isBalancedNaive(node.left) && isBalancedNaive(node.right);
}

function getHeight(node: TreeNode | null): number {
    if (node === null) return 0;
    return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

Complexity Analysis of Naive Approach

• Time Complexity: $\mathcal{O}(N^2)$ in the worst-case scenario (such as a skewed tree), because for each of the $N$ nodes, we traverse down its subtree to calculate heights, leading to nested linear operations.
• Space Complexity: $\mathcal{O}(N)$ auxiliary stack space for recursion.
• Verdict: Unacceptable for large datasets in production environments. We must eliminate the redundant height calculations.

4. The Optimized Approach: Merging Height Calculation with Balance Checking ($\mathcal{O}(N)$)

The Breakthrough Idea

To optimize the time complexity down to $\mathcal{O}(N)$, we need to compute the height of the tree and check for balance simultaneously in a single bottom-up post-order traversal.

Normally, a standard height-finding function returns an integer representing height. A boolean function returns true or false. How do we combine them?

State Encoding Trick:

• If a subtree is balanced, the function returns its actual height (an integer $\ge 0$).
• If a subtree is unbalanced, the function returns a sentinel flag value: -1.

By bubbling -1 up the call stack, any parent node instantly knows that a violation occurred deep below, allowing it to short-circuit and terminate early without performing unnecessary checks.

5. Step-by-Step Code Evolution

Optimized Recursive Function (checkHeight)

int checkHeight(TreeNode* node) {
    if (node == nullptr) return 0;

    // 1. Get left subtree height
    int leftHeight = checkHeight(node->left);
    if (leftHeight == -1) return -1; // Short-circuit if left is unbalanced

    // 2. Get right subtree height
    int rightHeight = checkHeight(node->right);
    if (rightHeight == -1) return -1; // Short-circuit if right is unbalanced

    // 3. Check current node balance condition
    if (abs(leftHeight - rightHeight) > 1) {
        return -1; // Mark current subtree as unbalanced
    }

    // 4. Return actual height if balanced
    return 1 + max(leftHeight, rightHeight);
}

6. Complete Implementation (C++ and Java)

Below are the complete, production-ready implementations in both C++ and Java.

C++ Implementation

#include <algorithm>
#include <cmath>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    int dfsHeight(TreeNode* node) {
        // Base case: empty tree has height 0
        if (node == nullptr) return 0;

        // Recursively check left subtree
        int leftHeight = dfsHeight(node->left);
        if (leftHeight == -1) return -1;

        // Recursively check right subtree
        int rightHeight = dfsHeight(node->right);
        if (rightHeight == -1) return -1;

        // Check balance condition for current node
        if (abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        // Return height of current node
        return 1 + max(leftHeight, rightHeight);
    }

public:
    bool isBalanced(TreeNode* root) {
        return dfsHeight(root) != -1;
    }
};

Java Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfsHeight(root) != -1;
    }

    private int dfsHeight(TreeNode node) {
        // Base case: empty tree has height 0
        if (node == null) return 0;

        // Recursively check left subtree
        int leftHeight = dfsHeight(node.left);
        if (leftHeight == -1) return -1;

        // Recursively check right subtree
        int rightHeight = dfsHeight(node.right);
        if (rightHeight == -1) return -1;

        // Check balance condition for current node
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        // Return height of current node
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

7. Dry Run Walkthrough

Consider checking the balance of this tree:

         1
        / \
       2   0
      /
     3

1. Call isBalanced(1) -> invokes dfsHeight(1).
2. dfsHeight(1) calls dfsHeight(2).
3. dfsHeight(2) calls dfsHeight(3).
4. dfsHeight(3) has left = null (returns 0) and right = null (returns 0).
   • Difference: |0 - 0| = 0 $\le 1$.
   • Returns height: 1 + max(0, 0) = 1 to node 2.
5. Back at dfsHeight(2): leftHeight = 1. Now calls right child: dfsHeight(null) which returns 0.
   • Difference: |1 - 0| = 1 $\le 1$.
   • Returns height: 1 + max(1, 0) = 2 to root node 1.
6. Back at root dfsHeight(1): leftHeight = 2. Now calls right child: dfsHeight(0).
   • Node 0 is a leaf node, returns height 1.
   • Difference at root 1: |leftHeight - rightHeight| = |2 - 1| = 1 $\le 1$.
   • Returns height: 1 + max(2, 1) = 3.
7. Final Result: dfsHeight(root) returns 3 (not -1), so isBalanced returns true.

8. Complexity Summary Table

9. Summary and Key Takeaways

• Definition of Balance: A binary tree is balanced if for every node, the height difference between its left and right subtrees is at most 1.
• Avoid Redundant Work: Naive solutions recalculate subtree heights repeatedly, resulting in an inefficient $\mathcal{O}(N^2)$ time complexity.
• State Encoding Pattern: By letting height-checking functions return -1 upon detecting an imbalance, we combine validation and height computation into a single pass.
• Optimal Efficiency: The optimized recursive algorithm visits each node exactly once, achieving an optimal $\mathcal{O}(N)$ time complexity.
• Short-Circuiting: As soon as a -1 sentinel value is encountered, recursion halts further traversal up the call stack, saving CPU cycles.
• Space Complexity Reality: While time complexity drops to $\mathcal{O}(N)$, stack memory remains $\mathcal{O}(N)$ in the worst case (e.g., skewed trees).