The O(n) Club: Symmetric Trees — Why Your Left Nodes Need Couples Therapy

The O(n) Club: Symmetric Trees — Why Your Left Nodes Need Couples Therapy

⚡ TL;DR

Ever wonder if your binary tree is as balanced and symmetrical as your morning coffee routine? Check if your tree is a mirror image of itself — and don’t just compare each side like twins, compare them like left and right socks. Brute force? Serialize both subtrees or run two traversals. But recursion is what every self-respecting dev and their interviewer want you to use. Here’s a fast flavor:

// Java - Mirror in the Morning
public boolean isSymmetric(TreeNode root) {
    return root == null || isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    if (a.val != b.val) return false;
    return isMirror(a.left, b.right) && isMirror(a.right, b.left);
}

🧠 How Devs Usually Mess This Up

Most folks treat this as a boring equality check: compare left with left, right with right — like a mirror means a photocopier. (Spoiler: it doesn’t.) They forget that the left node’s left needs to match the right node’s right. And then there’s the Null Fumble: one side is a node, the other is null, and suddenly their tree is the logical equivalent of a lopsided IKEA desk.

🔍 What’s Actually Going On

Imagine showing your family a Rorschach inkblot — if you folded it in half, every blob needs to land on its equal-but-opposite friend. That’s the comparison at every level. The left subtree’s left node is married to the right subtree’s right node (and vice versa), all the way down the branch family tree until you hit leaves or nulls.

🛠️ PseudoCode

• Start: If root is null, it’s symmetric. (Null is always chill.)
• Begin check: Compare root.left and root.right.
• For nodes a and b:
  • If both null, they’re soulmates. (Symmetry holds here.)
  • If one null, romance is dead, tree isn’t symmetric.
  • If values don’t match, instant disqualification.
  • Otherwise, keep going like a stubborn therapist:
    

    return isMirror(a.left, b.right) && isMirror(a.right, b.left);

    The left child of a must be the right child of b, and vice versa. Mirror, not pirate copy.

💻 The Code

// Classic Recursion
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || isMirror(root.left, root.right);
    }
    private boolean isMirror(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        if (a.val != b.val) return false;
        return isMirror(a.left, b.right) && isMirror(a.right, b.left);
    }
}
 // Iterative (Because Recursion Stacks Have Limits)
import java.util.*;
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue
<treenode> q = new LinkedList<>();
        q.add(root.left);
        q.add(root.right);
        while (!q.isEmpty()) {
            TreeNode a = q.poll(), b = q.poll();
            if (a == null && b == null) continue;
            if (a == null || b == null) return false;
            if (a.val != b.val) return false;
            q.add(a.left);   q.add(b.right);
            q.add(a.right);  q.add(b.left);
        }
        return true;
    }
}</treenode>

⚠️ Pitfalls, Traps & Runtime Smacks

• Forgetting to check for nulls: null == null is fine, but null != node kills your symmetry dreams fast.
• Comparing the root to itself: The real party starts at root.left vs root.right. The root is always symmetric (unless you really break things).
• Stack explosions: Deep recursion? DFS stack is O(h), BFS queue can balloon to O(n) for wide trees. Blame your tree’s awkward adolescence.
• Complexity Math: No matter what, you visit everyone once. That’s O(n) time, O(h) space for recursion (h = tree height), O(n) for BFS queues.

🧠 Interviewer Brain-Tattoo

Symmetry isn’t “copies on both sides”—it’s opposites perfectly balanced, kind of like prod and staging… until someone pushes a hotfix on Friday.