LeetCode 101 – Symmetric Tree

Symmetric Tree is Same Tree with two characters changed, and it is worth doing immediately after it for exactly that reason. The insight is small and complete: a tree is symmetric when its left subtree mirrors its right, and "mirrors" means compare left against right and right against left.

The problem

Given the root of a binary tree, return whether it is a mirror image of itself around its centre.

      1
     / \
    2   2          -> true
   / \ / \
  3  4 4  3

      1
     / \
    2   2          -> false   the 3s are on the same side, not mirrored
     \    \
      3    3

  []               -> true    an empty tree is symmetric
  [1]              -> true

One node cannot be checked alone

Symmetry is not a property of a node, it is a property of a pair of nodes. So the recursion cannot take one argument — it takes two, and asks whether those two subtrees mirror each other:

mirror(a, b):
    both null            -> true
    exactly one null     -> false
    a.val != b.val       -> false
    mirror(a.left,  b.right)      <- crossed
    mirror(a.right, b.left)       <- crossed

Those first three lines are Same Tree verbatim, base cases and ordering included. The only difference is in the recursive step: Same Tree pairs left with left and right with right; this pairs left with right and right with left.

Being able to say "this is Same Tree with the children crossed" is the whole answer, and it is a better answer than deriving it from scratch — it shows you recognise structure rather than re-solving.

Java

class Solution {
    public boolean isSymmetric(TreeNode root) {
        // A single node is trivially its own mirror; compare its two subtrees.
        return root == null || mirror(root.left, root.right);
    }

    private boolean mirror(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 mirror(a.left, b.right)     // crossed: outer pair
            && mirror(a.right, b.left);   // crossed: inner pair
    }
}

The public method exists only to turn one root into the pair the recursion needs. That split — a wrapper that sets up the arguments, and a helper that does the work — is the standard shape whenever the recursive signature differs from the one you were given.

The two recursive calls are the outer pair and the inner pair of the four grandchildren. Naming them that way in a comment makes the crossing obvious to a reader who has not seen the trick.

Python

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def mirror(a: TreeNode, b: TreeNode) -> bool:
            if a is None and b is None:
                return True
            if a is None or b is None:
                return False
            if a.val != b.val:
                return False
            return mirror(a.left, b.right) and mirror(a.right, b.left)

        return root is None or mirror(root.left, root.right)

The wrong answer worth knowing about

A tempting shortcut is to take the inorder traversal and check whether it is a palindrome. It is fast, it is short, and it is wrong:

      1
     / \
    2   2          inorder: 2, 2, 1, 2, 2   -- a palindrome
   /   /
  2   2            but NOT symmetric: both 2s hang on the LEFT.
                   A mirror would need the right-hand one on the right.

Traversal order throws away the structural information the question is asking about, and adding null markers to the traversal patches this particular case without making the approach sound. If you raise the idea, raise the counterexample with it — proposing it and then killing it yourself reads much better than being shown the failure.

The iterative version

Queue the nodes in the order they need to be compared, two at a time:

    boolean isSymmetricIterative(TreeNode root) {
        if (root == null) return true;

        Deque<TreeNode[]> queue = new ArrayDeque<>();
        queue.add(new TreeNode[]{root.left, root.right});

        while (!queue.isEmpty()) {
            TreeNode[] pair = queue.poll();
            TreeNode a = pair[0], b = pair[1];

            if (a == null && b == null) continue;      // this pair matches
            if (a == null || b == null) return false;
            if (a.val != b.val) return false;

            queue.add(new TreeNode[]{a.left, b.right});   // same crossing
            queue.add(new TreeNode[]{a.right, b.left});
        }

        return true;
    }

The continue where the recursion had return true is the same substitution as in Same Tree: a matching empty pair means "nothing further to check here", not "the whole answer is true".

Complexity

Every node is part of exactly one comparison pair, so both are linear, and both exit early on the first mismatch.

The pattern

Two pointers walked through one structure in opposite directions is the same idea that makes Valid Palindrome (125) and the two-pointer half of 3Sum work — this is the tree version. Invert Binary Tree (226) swaps the children outright, after which symmetry is just Same Tree against the original.

The general move: when a property relates two positions rather than describing one, make the recursion take both.

What the interviewer is checking

• That the recursion takes two nodes, not one.
• The crossing — a.left with b.right, a.right with b.left.
• The same three base cases as Same Tree, in an order where each protects the next.
• Empty tree and single node.
• That you connect it to Same Tree rather than deriving it cold.
• If you propose the palindrome shortcut, that you also kill it.