101 · Symmetric Tree

The same machine as LC 100 with the recursion crossed: (a.left, b.right) and (a.right, b.left). Which children get paired is a parameter of the algorithm, not a law of it — that is the entire lesson of this problem.

1 — The problem

Is the tree a mirror of itself about its root? The reframing that makes it trivial: a tree is symmetric exactly when its left subtree is a mirror of its right subtree. That is a two-tree question, so it is a sub-variant B problem, and the single-argument isSymmetric becomes a one-line wrapper over a two-argument helper.

One row differs. If you find yourself writing new base cases for this problem, you have not noticed that it is LC 100 with two arguments swapped.

2 — Watching the cursors cross

Two cursors walk the same tree in opposite directions. Cursor a goes left where cursor b goes right, so they stay reflections of each other at every step. Follow the pair down to the 3s: a reaches the outer-left 3 by going left–left, while b reaches the outer-right 3 by going right–right.

Notice that the two cursors are never at the same node, and never both in the same subtree after the first call. They partition the tree between them — which is why this costs one pass, not two.

2.1 The near-miss that catches the wrong answer

A tempting shortcut: collect the inorder traversal and check whether it reads the same backwards. It is wrong, and the standard counterexample is small:

Values alone cannot carry structure. Any approach that flattens the tree before comparing has thrown away the very thing being asked about — the same reason LC 297 needs explicit null markers.

2.2 The iterative version

Because the recursion only ever handles a pair at a time, it converts to a queue mechanically — push pairs, pop pairs, push the two crossed pairings:

public boolean isSymmetric(TreeNode root) {
    Deque<TreeNode> q = new ArrayDeque<>();
    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);   // crossed, exactly as in the recursion
        q.add(a.right); q.add(b.left);
    }
    return true;
}

ArrayDeque rejects null elements, so use LinkedList if you want to enqueue nulls literally — or restructure to enqueue only non-null pairs. This is a real compile-clean, runtime-fail trap.

3 — Complexity and edge cases

• Time O(n) — each node participates in exactly one pair. Space O(h) recursive, O(n) for the queue version.
• Empty tree: symmetric. The wrapper calls isMirror(null, null), which the first base case answers true — so no null check is needed on root itself, provided the wrapper does not dereference it. root.left does dereference it, so guard the wrapper if the input may be null.
• Single node: symmetric — both subtrees are null.
• Common bug: crossing only one of the two calls. Writing isMirror(a.left, b.right) && isMirror(a.right, b.right) compiles, runs, and is right on small symmetric inputs.
• Common bug: calling isSame(root.left, root.right) by mistake — that tests whether the two halves are identical, not mirrored. On a tree whose subtrees are both palindromic it accidentally agrees.

4 — Reference implementation

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;
    return a.val == b.val
        && isMirror(a.left,  b.right)   // outer pair
        && isMirror(a.right, b.left);   // inner pair
}