Balanced Binary Tree

Problem Link

Balanced Binary Tree – LeetCode

Problem: Balanced Binary Tree

Problem Statement

Given a binary tree, determine if it is height-balanced.

A binary tree is balanced if the depth of the two subtrees of every node never differs by more than 1.

Examples

Example 1

Input:

      3
     / \
    9  20
       /  \
      15   7

Output: true

Example 2

Input:

      1
     / \
    2   2
   / \
  3   3
 / \
4   4

Output: false

Constraints

• The number of nodes in the tree is in the range [0, 5000]

• -10⁴ <= Node.val <= 10⁴

Intuition

We must determine if each node has left and right subtrees with height difference ≤ 1, and all such subtrees are balanced.

A brute-force approach:

• Check balance at each node by computing left and right heights → leads to O(N²)

A better solution:

• Use post-order traversal and for each node:

  • Return height if subtree is balanced

  • If not balanced, propagate a special value (-1) upward to indicate imbalance

Approach (Recursion using Induction – Base Case – Hypothesis)

1. Base Case:

If the node is null, return height 0

2. Hypothesis:

Assume checkBalance(node.left) and checkBalance(node.right) return:

• valid height if subtree is balanced

• -1 if subtree is not balanced

3. Induction:

• If either child is -1, propagate -1 upward

• If height difference > 1, return -1

• Else, return 1 + max(leftHeight, rightHeight)

Code (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

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

    private int checkBalance(TreeNode node) {
        if (node == null) return 0;

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

        if (left == -1 || right == -1) return -1;
        if (Math.abs(left - right) > 1) return -1;

        return 1 + Math.max(left, right);
    }
}

Time and Space Complexity

• Time Complexity: O(N)
  Each node is visited once.

• Space Complexity: O(H)
  Due to recursion stack, where H is the height of the tree (O(log N) for balanced, O(N) for skewed).

Dry Run

Input:

      1
     / \
    2   2
   / 
  3   
 / 
4

At node 4 → height = 1
At node 3 → left = 1, right = 0 → OK
At node 2 → left = 2, right = 0 → imbalance → return -1
At root → imbalance → return false

Conclusion

This problem demonstrates:

• Efficient bottom-up recursion

• How to propagate failure (-1) in recursion

• Post-order traversal for checking tree properties