The O(n) Club: Balanced Binary Tree: Don’t Let Your Code Topple Over

The O(n) Club: Balanced Binary Tree: Don’t Let Your Code Topple Over

⚡ TL;DR

If you only glance at the root of your binary tree, you might as well check if a shelf is sturdy by poking one end. You need to check every node to call a tree balanced. Combining height calculation and balance-checking in one recursion is your ticket to a fast O(n) solution. Java snippet?

// Quick Java flavor:
boolean isBalanced(TreeNode root) {
    return check(root) != -1;
}
int check(TreeNode node) {
    if (node == null) return 0;
    int left = check(node.left);
    if (left == -1) return -1;
    int right = check(node.right);
    if (right == -1) return -1;
    if (Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
}

🧠 How Devs Usually Mess This Up

Some folks think if the root seems balanced, the whole tree must be too—like judging your apartment’s wifi by standing right next to the router. Others lovingly recompute subtree heights for every node, sending your algorithm straight to O(n²) purgatory. And yes, null nodes (or empty subtrees) are balanced and, for once, require absolutely zero stress.

🔍 What’s Actually Going On

Picture stacking soup cans: If one level is out of whack, the next grocery catastrophe is inevitable. A balanced binary tree means every node’s left and right subtrees differ in height by no more than one. That’s it. By folding height calculation and balance-checking into one DFS pass, you can abandon the operation early if you find a lopsided branch—the tree-processing equivalent of dropping everything when you realize there’s no coffee left.

🛠️ PseudoCode

• Base case: Return 0 for a null node (empty subtree = chill).
• Check left height: Recursively solve for left subtree.
  int left = check(node.left);
• Spot imbalance: If left == -1, the left subtree already toppled—bail immediately.
• Check right height: Repeat process on right subtree.
  int right = check(node.right);
• Spot more imbalance: If right == -1, bail again.
• Evaluate current wobble: If abs(left – right) > 1, node is unbalanced—send -1 behind the scenes all the way up.
• Still standing? Return height as max(left, right) + 1.
• Final verdict: If main call returns -1, your tree needs counseling; otherwise, all good.

💻 The Code

// 'TreeNode' class gets you through Leetcode and life.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 public class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
    private int height(TreeNode node) {
        if (node == null) return 0;
        int left = height(node.left);
        if (left == -1) return -1;
        int right = height(node.right);
        if (right == -1) return -1;
        if (Math.abs(left - right) > 1) return -1;
        return Math.max(left, right) + 1;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Root-only check? Great for kindergarten, not for interviews or actual trees.
• Redundant recursion? Running height() on subtrees repeatedly means you like wasting time. Stop it.
• ‘Null’ isn’t scary: Returning height 0 for null nodes is correct. Don’t debug this. Embrace it.
• Early returns matter: Spot a -1? Leave immediately. Don’t do “just one more” traversal.
• Time Complexity: O(n) – every node gets one respectful visit.
  Space Complexity: O(h) – that’s stack frames, not memory leaks.

🧠 Interviewer Brain-Tattoo

If you only care about balancing the root, your next job interview might only care about your first answer.