4. Balanced Binary Tree

Description

Balanced Binary Tree
Given a binary tree, determine if it is A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one..

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:
Input: root = []
Output: true

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -104 <= Node.val <= 104

Approach

• We will return -1 if it is not balanced and rest is simple dfs recursion

class Solution {
    public boolean isBalanced(TreeNode root) {
        return check(root) != -1;
    }
 
    public int check(TreeNode root) {
        if (root == null)
            return 0;
 
        int left = check(root.left);
        int right = check(root.right);
 
        if (left == -1 || right == -1 || Math.abs(left - right) > 1)
            return -1;
 
        return 1 + Math.max(left,right);          
    }
}

Approach 1: Bottom-Up Recursive DFS ($O(N)$ Time, $O(N)$ Space)

Intuition

Calculate the height of left and right subtrees recursively. If any subtree is found to be unbalanced (height difference $>1$), return -1 to immediately short-circuit and propagate the failure upward.

1. If node is null, return height 0.
2. Recursively check checkHeight(node.left) and checkHeight(node.right). If either returns -1, return -1.
3. If Math.abs(leftHeight - rightHeight) > 1, return -1 (unbalanced).
4. Otherwise, return 1 + Math.max(leftHeight, rightHeight).

class Solution {
    public boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }
 
    private int checkHeight(TreeNode node) {
        if (node == null) return 0;
 
        int leftHeight = checkHeight(node.left);
        if (leftHeight == -1) return -1; // Short-circuit left subtree
 
        int rightHeight = checkHeight(node.right);
        if (rightHeight == -1) return -1; // Short-circuit right subtree
 
        // If height difference exceeds 1, tree is unbalanced
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
 
        return 1 + Math.max(leftHeight, rightHeight);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every node is visited at most once; short-circuits early on unbalanced subtrees.
• Space Complexity: $O(N)$ worst-case call stack depth for a skewed tree ($O(\log N)$ for a balanced tree).

---

Approach 2: Iterative Postorder Traversal with Map ($O(N)$ Time, $O(N)$ Space)

Intuition

Use the standard single-stack postorder traversal template (lastVisited pointer) while tracking subtree heights in a Map<TreeNode, Integer>.

1. Traverse left branches to the leaf nodes.
2. When popping a node from the stack (after both child subtrees have been processed), retrieve leftHeight and rightHeight from heights.
3. If Math.abs(leftHeight - rightHeight) > 1, immediately return false.
4. Otherwise, store 1 + Math.max(leftHeight, rightHeight) into heights for the current node.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
 
        Deque<TreeNode> stack = new ArrayDeque<>();
        Map<TreeNode, Integer> heights = new HashMap<>();
        TreeNode curr = root;
        TreeNode lastVisited = null;
 
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
 
            TreeNode peekNode = stack.peek();
            if (peekNode.right != null && lastVisited != peekNode.right) {
                curr = peekNode.right;
            } else {
                stack.pop();
                int leftHeight = heights.getOrDefault(peekNode.left, 0);
                int rightHeight = heights.getOrDefault(peekNode.right, 0);
 
                if (Math.abs(leftHeight - rightHeight) > 1) {
                    return false;
                }
 
                heights.put(peekNode, 1 + Math.max(leftHeight, rightHeight));
                lastVisited = peekNode;
            }
        }
 
        return true;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every node is pushed, popped, and evaluated in $O(1)$ time.
• Space Complexity: $O(N)$ — Space required for the explicit stack and the node-to-height map.

---

Easy Memory Rule

“Calculate node heights bottom-up $\to$ If Math.abs(leftHeight - rightHeight) > 1 return -1 / false!”

Roles of curr and peekNode

• curr (The Explorer / Downward Navigator):
  Controls the downward traversal phase. As long as curr != null, it drives the loop to push nodes onto the stack and dive as deep left as possible.
• peekNode (The Inspector / Parent Checkpoint):
  Inspects the node currently at the top of the stack without removing it. It checks whether the node’s right subtree is already processed or still needs to be explored.

---

Why peek() and NOT pop() Initially?

In Postorder Traversal ($\text{Left}\to \text{Right}\to \text{Root}$), a parent node can only be processed after both its left and right subtrees are completely finished.

When you reach the bottom of a left branch, the top of the stack holds a parent node whose left child was just processed.

1. If you pop() immediately: You permanently remove the parent from the stack. If that parent happens to have a right child that hasn’t been visited yet, you lose your reference to return to this parent later.
2. Because you peek() first: You safely inspect the parent node to make a 2-way decision:
   • Case A (Right subtree pending): peekNode.right != null && lastVisited != peekNode.right
     • You keep the parent on the stack and pivot right: curr = peekNode.right.
   • Case B (Both subtrees done): peekNode.right == null OR lastVisited == peekNode.right
     • Now it is safe to pop()! You remove the parent, compute its height using the map, check balance, and update lastVisited = peekNode.

---

Interview One-Liner Summary

“We peek() to inspect if the right child needs exploring first. We only pop() once both left and right subtrees are confirmed finished, satisfying the Postorder ($\text{Left}\to \text{Right}\to \text{Root}$) requirement.”