The O(n) Club: Invert Binary Tree – Mirror Mayhem and Recursive Therapy

The O(n) Club: Invert Binary Tree – Mirror Mayhem and Recursive Therapy

⚡ TL;DR

Take a binary tree and swap every left and right child—recursively—until the whole thing looks like it tried to read itself in the bathroom mirror. Classic brute-force is just: recurse, swap, return. Java makes this mildly painless:

// Java, short and sweet
public TreeNode invertTree(TreeNode root) {
  if (root == null) return null;
  TreeNode temp = root.left;
  root.left = invertTree(root.right);
  root.right = invertTree(temp);
  return root;
}

🧠 How Devs Usually Mess This Up

Common binary tree inverting fails:

• Partial Swap Syndrome: Only swap at the root, then forget to go deeper. Your tree is now “inverted” in the most disappointing way possible.
• Value Reversal Confusion: No, “invert” does not mean reverse every node’s value like a sad array.
• Senior Overengineering: Crafting a shiny new tree from scratch and burning CPU cycles—just to avoid pointer swaps. Sometimes simple is smarter.
• Null Blindness: Skipping null checks like you’re speedrunning bugs straight to the stack overflow leaderboard.

🔍 What’s Actually Going On

Imagine your binary tree is a quirky family portrait. The parent stands in the middle, left child photobombs on the left, right child nervously on the right. You turn the entire frame around: everyone’s positions, all the way down, invert. It’s not just a surface swap—every branch gets this mirror moment, recursively, until even the lowest leaf has switched sides.

For coders: swap left and right pointers, recurse, and call it a day. Recursion does the heavy lifting (like an unpaid intern with perfect memory). If you’re brave, iterative stack-based inversion works, but recursion’s usually neater unless your tree is taller than your caffeine tolerance.

🛠️ PseudoCode

• Base Case:

  if (root == null) return null;

  Stop at the end of every branch. Don’t invert empty air.
• Invert Left & Right Children:

  TreeNode left = invertTree(root.left);
  TreeNode right = invertTree(root.right);

  Let recursion handle the kids before forcing them to switch rooms.
• Swap!

  root.left = right;
  root.right = left;

  The old switcheroo. Classic!
• Return the Root:

  return root;

  So your parent node doesn’t disown its family tree.

💻 The Code

// Tree node definition
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}
 public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        return root;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Nulls Galore: Always check root == null or risk a call stack meltdown.
• Leaf Freakout: Don’t assume left/right children exist. Not all branches have two buddies.
• Recursion Stack: Worst-case (stick-tree!) eats up O(h) space; if your tree’s a broomstick, watch for StackOverflowError.
• Runtime: Every node gets visited once—just once. That’s glorious O(n) time.

🧠 Interviewer Brain-Tattoo

“Invert the tree’s structure, not just its attitude. You’re flipping pointers, not flipping out.”