Bottom-Up DFS (Single Pass)

A naive top-down approach computes height repeatedly for the same subtrees — O(n log n) for balanced, O(n²) for skewed. The optimal approach is a single bottom-up DFS pass that simultaneously computes height and checks balance, using the sentinel value -1 to propagate imbalance up the call stack.

Algorithm:

• If the node is null, return height 0.
• Recursively get the height of the left subtree; if it returns -1, propagate -1 upward.
• Recursively get the height of the right subtree; if it returns -1, propagate -1 upward.
• If |leftHeight - rightHeight| > 1, return -1 (imbalanced signal).
• Otherwise return 1 + Math.max(leftHeight, rightHeight).

public boolean isBalanced(TreeNode root) { return checkHeight(root) != -1; } // Returns height if subtree is balanced, -1 if imbalanced private int checkHeight(TreeNode node) { if (node == null) return 0; int leftHeight = checkHeight(node.left); if (leftHeight == -1) return -1; // propagate imbalance int rightHeight = checkHeight(node.right); if (rightHeight == -1) return -1; // propagate imbalance if (Math.abs(leftHeight - rightHeight) > 1) { return -1; // current node is imbalanced } return 1 + Math.max(leftHeight, rightHeight); } This single-pass approach is O(n) because each node is visited exactly once. The -1 sentinel short-circuits processing of subtrees once an imbalance is detected.

• Time: O(n) — each node is visited exactly once in the bottom-up DFS.
• Space: O(h) — recursion stack depth equals the tree height h (O(log n) balanced, O(n) skewed).