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:

🧠 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

Return the Root:

return root;

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

Swap!

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

The old switcheroo. Classic!

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.

Base Case:

if (root == null) return null;

Stop at the end of every branch. Don’t invert empty air.

💻 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.