A balanced binary tree is one where the heights of the two subtrees of every node differ by no more than one. This ensures that the tree is as flat as possible, which helps maintain efficient operations like search, insert, and delete. In this problem, we need to determine if a given binary tree is balanced.
Top-Down Recursion (Naive)
- Starts at the root and passes information down the tree.
- Often uses preorder traversal (process root before its subtrees)
- The computation flows from parent to child.
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (Math.abs(leftHeight - rightHeight) > 1) return false;
return isBalanced(root.left) && isBalanced(root.right);
}
private int height(TreeNode node) {
if (node == null) return 0;
return Math.max(height(node.left), height(node.right)) + 1;
}- At each node, check if the height difference between its left and right subtrees is greater than 1.
- Compute the height of the left and right subtrees and check if the difference exceeds 1.
- Repeat this process for all nodes in the tree.
Key Points
• Time Complexity: O(n²) in the worst case:
• Each recursive isBalanced call traverses all nodes below it to compute heights.
• Space Complexity: O(h) due to recursion stack.
• Why Top-Down?:
• Conceptually simple.
• Directly checks balance at each node.
Bottom-Up Approach (Optimized)
- Starts at the leaves and combines results up to the root.
- Often uses postorder traversal (process subtrees before the root).
- The computation flows from children to parent.
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;
int rightHeight = checkHeight(node.right);
if (rightHeight == -1) return -1;
if (Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight, rightHeight) + 1;
}1. Recursively calculate the height of the left and right subtrees.
2. If a subtree is unbalanced, return -1 immediately.
3. Use the subtree heights to check the balance of the current node.
4. Propagate the results upward, combining height calculations with balance checks.
Why Bottom-Up is Preferred
1. Early Termination: Unbalanced subtrees stop further computation, saving time.
2. Combined Calculation: Height and balance are calculated together, reducing redundant work.
3. Optimal for Large Trees: Handles deeply nested or large trees efficiently without stack overflow.
Conclusion
• Top-Down is intuitive but inefficient due to redundant height calculations.
• Bottom-Up is efficient and aligns with best practices for recursive problems in competitive programming and LeetCode.
