Symmetric Tree LeetCode 101 Deep Dive

LeetCode 101 Symmetric Tree asks a deceptively simple question: given the root of a binary tree, check whether it is a mirror image of itself. A symmetric tree looks the same when you fold it along its central vertical axis — the left branch mirrors the right branch at every level.

This problem is foundational in tree recursion. It appears frequently in technical interviews at Google, Amazon, and Meta as a warm-up for more complex tree comparison problems. If you can articulate the mirror definition precisely and implement it cleanly, you demonstrate strong tree intuition.

The constraints are tight but standard: the number of nodes is between 1 and 1000, and node values range from -100 to 100. You are expected to implement both recursive and iterative solutions — interviewers often ask for both.

A tree is symmetric if and only if its left subtree is a mirror reflection of its right subtree. But what does "mirror" mean precisely? Two subtrees are mirrors of each other if their root values match, AND the left child of one mirrors the right child of the other — and vice versa.

The formal definition is recursive: mirror(left, right) holds when left.val == right.val, AND mirror(left.left, right.right) is true, AND mirror(left.right, right.left) is true. Notice the cross-pairing: left.left pairs with right.right, and left.right pairs with right.left. This is the structural heart of the problem.

A common mistake is to check if left.left == right.left (same side) or to compare the left subtree with itself. Symmetry is not about identical halves — it is about mirrored halves. The cross-comparison is the key insight that distinguishes this from Same Tree.

The recursive solution maps directly onto the mirror definition. Write a helper isMirror(left, right) that returns true when the two subtrees are mirrors. Base cases handle the null scenarios: if both nodes are null, the subtrees are trivially mirrored (return true); if exactly one is null, they cannot be mirrors (return false).

The recursive case checks three conditions joined by AND: the values must match, the outer pair (left.left, right.right) must be mirrors, and the inner pair (left.right, right.left) must be mirrors. The main isSymmetric function simply calls isMirror(root.left, root.right).

Time complexity is O(n) because every node is visited exactly once. Space complexity is O(h) where h is the tree height — the recursion stack depth equals the height. For a balanced tree that is O(log n), but for a skewed tree (worst case) it degrades to O(n).

The iterative solution uses a queue that stores pairs of nodes to compare. Begin by enqueuing (root.left, root.right). On each iteration, dequeue a pair; if both are null, continue. If exactly one is null, return false. If their values differ, return false. Otherwise, enqueue two new pairs: (left.left, right.right) and (left.right, right.left).

This approach processes mirror-pairs level by level, mirroring the recursive logic without the call stack. The queue always contains pairs of nodes that should be mirrors of each other. When the queue is exhausted without a mismatch, the tree is symmetric.

Space complexity is O(w) where w is the maximum width of the tree — the maximum number of node pairs that can be in the queue simultaneously. For a balanced tree this is O(n/2) = O(n). The iterative approach avoids stack overflow issues for very deep trees where recursion depth could become problematic.

Symmetric Tree sits at the intersection of two other classic problems: Same Tree (LeetCode 100) and Invert Binary Tree (LeetCode 226). The relationship is illuminating: a tree is symmetric if and only if it equals its own mirror image. In code: isSymmetric(root) == isSameTree(root, invertTree(root)).

The recursive skeleton used in isMirror is nearly identical to the one used in isSameTree — both check two nodes for structural equality with matching values. The only difference is the cross-pairing in mirror versus the same-side pairing in same-tree.

Understanding this family of problems accelerates your preparation. Once you internalize the recursive structure (check two nodes, recurse on their children with some pairing rule), you can adapt it to subtree checks, tree serialization comparisons, and more advanced structural queries.

In Python, the recursive solution is six lines. Define isMirror inside isSymmetric as a nested function or as a standalone helper. The iterative version uses collections.deque: append (root.left, root.right) as a tuple, popleft on each iteration, and append two new pairs for each valid match.

In Java, the recursive approach is essentially the same structure. The iterative version uses a LinkedList as a Queue, but instead of storing pairs as tuples you interleave them — poll two nodes at a time. Enqueue node1.left, node2.right, then node1.right, node2.left to preserve the mirror-pair ordering.

Both recursive and iterative solutions run in O(n) time and O(h) or O(w) space respectively. The recursive solution is more readable and easier to explain in an interview. The iterative solution demonstrates depth of understanding and handles stack overflow concerns for pathological inputs.

Symmetric Tree is part of a broader family of tree comparison problems that all use the same recursive pair-checking skeleton. Same Tree (100) checks if two trees are structurally identical with matching values. Subtree of Another Tree (572) checks if one tree appears as a subtree within another — it calls isSameTree as a subroutine at every node.

Invert Binary Tree (226) is the structural transformation underlying symmetry — inverting a tree and checking if it equals the original is functionally equivalent to checking symmetry. Understanding this connection helps you see why the cross-pairing in isMirror works.

For interview preparation, treat these four problems — Symmetric Tree, Same Tree, Invert Binary Tree, and Subtree of Another Tree — as a single concept cluster. Master one and the others follow naturally. The recursive skeleton is the same; only the pairing rule and base conditions change.