Definition
- Height-balanced – for every node,
|leftHeight - rightHeight| <= 1. - Efficient approach – a single post-order recursion returns each subtree's height, or -1 (sentinel) the moment any imbalance is found.
- Short-circuit – once -1 is returned, it propagates immediately without further computation.
- Naive approach – computes height separately at every node; O(n * h) time, quadratic on skewed trees.
- Complexity – efficient approach is O(n) time, O(h) space.
Think of the National Bank of India's reporting tree and a rule that no manager's two sides should be lopsided: one branch of reports cannot be much deeper than the other. Each manager compares how deep their left team goes versus their right team. If any manager's two sides differ by more than one level, the whole structure is declared unbalanced.
Understanding the Concepts
What does it mean for a binary tree to be balanced?
A binary tree is height-balanced when, at every single node, the heights of its left and right subtrees differ by at most one. This property ensures that the tree does not degenerate into a long chain, which would make operations like search degrade from O(log n) to O(n).
package com.bank.model;
public class AccountIndexNode {
public String accountNumber;
public AccountIndexNode left;
public AccountIndexNode right;
public AccountIndexNode(String accountNumber) {
this.accountNumber = accountNumber;
}
}
How does the efficient fused approach work?
Write a helper that returns the height of a subtree, or -1 if any part of it is unbalanced. Recurse left, check for sentinel, recurse right, check for sentinel, compare heights, and return.
package com.bank.service;
import com.bank.model.AccountIndexNode;
public class BalanceChecker {
public static boolean isBalanced(AccountIndexNode root) {
return checkHeight(root) != -1;
}
private static int checkHeight(AccountIndexNode node) {
if (node == null) return 0;
int left = checkHeight(node.left);
if (left == -1) return -1; // short-circuit
int right = checkHeight(node.right);
if (right == -1) return -1; // short-circuit
if (Math.abs(left - right) > 1) return -1; // imbalanced here
return 1 + Math.max(left, right); // height of this subtree
}
public static void main(String[] args) {
// ACC-100
// / \
// ACC-050 ACC-150
// /
// ACC-025
// /
// ACC-010
AccountIndexNode root = new AccountIndexNode("ACC-100");
root.left = new AccountIndexNode("ACC-050");
root.right = new AccountIndexNode("ACC-150");
root.left.left = new AccountIndexNode("ACC-025");
root.left.left.left = new AccountIndexNode("ACC-010");
System.out.println("Is balanced: " + isBalanced(root));
}
}
Is balanced: false
Why is the naive approach quadratic?
The naive approach computes the height of every node's subtrees with a separate recursion and checks the difference. This recomputes heights repeatedly. On a skewed tree (n nodes in a straight line), the height computation at the root is O(n), at its child O(n-1), and so on, giving O(n^2) total.
// NAIVE: O(n*h) time, quadratic on skewed trees
public static boolean isBalancedNaive(AccountIndexNode node) {
if (node == null) return true;
int leftH = height(node.left);
int rightH = height(node.right);
return Math.abs(leftH - rightH) <= 1
&& isBalancedNaive(node.left) // recomputes heights below
&& isBalancedNaive(node.right); // recomputes heights below
}
private static int height(AccountIndexNode node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
How does the sentinel short-circuit work?
Once any subtree is found unbalanced, the helper returns -1 immediately. The parent checks for -1 before recursing into the other child, so no further height computation happens. This early exit is what keeps the fused approach linear.
// Short-circuit flow:
int left = checkHeight(node.left);
if (left == -1) return -1; // stop immediately, do not recurse right
int right = checkHeight(node.right);
if (right == -1) return -1; // stop immediately, do not check abs diff
What are the edge cases?
Empty tree (balanced), single node (balanced), perfectly balanced tree, and a tree that is balanced at the root but unbalanced deeper.
package com.bank.service;
import com.bank.model.AccountIndexNode;
public class BalanceEdgeCases {
public static void main(String[] args) {
// Empty
System.out.println("Empty: " + BalanceChecker.isBalanced(null));
// Single
System.out.println("Single: " + BalanceChecker.isBalanced(
new AccountIndexNode("ACC-100")));
// Balanced
AccountIndexNode bal = new AccountIndexNode("ACC-100");
bal.left = new AccountIndexNode("ACC-050");
bal.right = new AccountIndexNode("ACC-150");
System.out.println("Balanced: " + BalanceChecker.isBalanced(bal));
}
}
Empty: true
Single: true
Balanced: true
What is the time and space complexity?
| Approach | Time | Space |
|---|---|---|
| Naive (recompute heights) | O(n * h), quadratic on skew | O(h) |
| Fused with sentinel | O(n) | O(h) |
The fused approach visits each node at most once and the sentinel short-circuit means it can exit even earlier in practice.
How does this relate to AVL trees and red-black trees?
AVL trees and red-black trees are self-balancing binary search trees that maintain balance after every insertion and deletion. The balance check here is the same condition that AVL trees enforce (height difference at most 1 at every node). Red-black trees use a weaker balance condition that allows height differences up to 2x but is cheaper to maintain.
// AVL rotation happens when |leftHeight - rightHeight| > 1
// The balance check in this problem is the same test
if (Math.abs(left - right) > 1) {
// AVL tree would rotate here to restore balance
// Our checker just returns -1 (unbalanced)
}
What should a senior engineer know?
A senior engineer should explain why the fused approach is linear while the naive approach is quadratic, and point to the short-circuit as the mechanism that makes it efficient. The fused post-order pattern, computing height while checking a property, appears in many tree problems.
In production at National Bank of India, the account-number index is a binary search tree. After a batch of inserts, a health check confirms the index is still balanced. If not, the service schedules a rebalance job because a lopsided index drives lookups toward linear time.
// Production health check
if (!BalanceChecker.isBalanced(accountIndexRoot)) {
scheduler.submit(new RebalanceJob(accountIndexRoot));
alertService.send("Account index is unbalanced, rebalance scheduled.");
}
Visual Overview
Fused Height + Balance Check
ACC-100
/ \
ACC-050 ACC-150
/
ACC-025
/
ACC-010
Post-order visits:
ACC-010: left=0, right=0, diff=0, return 1
ACC-025: left=1, right=0, diff=1, return 2
ACC-050: left=2, right=0, diff=2 > 1 → return -1 (UNBALANCED)
ACC-100: left=-1 → short-circuit, return -1
Result: -1 → not balanced
Sentinel Short-Circuit Flow
checkHeight(ACC-100)
├─ checkHeight(ACC-050)
│ ├─ checkHeight(ACC-025)
│ │ ├─ checkHeight(ACC-010) → 1
│ │ └─ checkHeight(null) → 0
│ │ diff = 1, ok → return 2
│ └─ checkHeight(null) → 0
│ diff = 2 > 1 → return -1 ← imbalance detected!
└─ left == -1 → return -1 ← short-circuit, skip right subtree
Final: -1 → false
Key Takeaway
A binary tree is height-balanced when at every node the heights of its left and right subtrees differ by at most one. The naive approach computes heights separately at each node, which recomputes over and over and degrades to quadratic time on skewed trees. The efficient approach fuses height computation with the balance check in a single post-order pass.
The helper returns the subtree's height, or a sentinel of -1 the moment any imbalance is found. The sentinel propagates immediately: the parent checks for -1 before recursing further, so no unnecessary work is done after the first violation. This short-circuit is what keeps the algorithm linear.
The technique of fusing a property check with a value computation in a single recursive pass appears throughout tree problems: diameter, maximum path sum, and balance check all share this pattern.
In our banking system at National Bank of India, the account-number index is a binary search tree whose lookup speed depends on balance. After a batch of inserts, the health check uses this fused approach to confirm the index is still balanced. If it is not, the service schedules a rebalance job because a lopsided index drives lookups toward linear time, which is unacceptable for a high-traffic account service.
Remember one sentence: fuse height computation with a balance check in post-order, return -1 as a sentinel to short-circuit the moment any node is unbalanced.
---