Symmetric Tree

Given the root of a binary tree, return true if the tree is a mirror image of itself around a vertical line through the root, and false otherwise. Both the shape and the values must mirror: the left subtree must be the reflection of the right subtree.

Trees are written in level order, row by row from left to right, with null marking a missing child; for example [5,3,3,null,8] means 5 has children 3 and 3, and the left 3 has only a right child 8. An empty tree counts as symmetric.

Example 1

Example 2

Example 3

Constraints

• 0 <= number of nodes <= 1000
• -100 <= Node.val <= 100

Pattern Path · Trees: DFS · problem 85 of 169

Start simple

Build a mirrored copy of the tree and compare it with the original node by node (or compare level-order lists with each row reversed): O(n) time but O(n) extra memory for the copy.

The key idea

The whole tree is symmetric exactly when its left and right subtrees are reflections of each other, so the real question is: when are two trees a and b mirrors?

• If both are empty, yes. If only one is empty, no.
• Otherwise their roots must hold the same value, and the outer pair must mirror (a.left with b.right), and the inner pair must mirror (a.right with b.left).

That definition is already a recursive algorithm. Each node is visited once, as part of exactly one pair, and the recursion stops at the first mismatch.

The same pairing works iteratively: push (root.left, root.right) onto a queue, and each time you pop a matching pair, push its outer pair and inner pair. This avoids deep recursion on very tall trees.

Complexity

• Time: O(n)
• Space: O(h) recursion depth, where h is the tree height

Python

class Solution:
    def isSymmetric(self, root):
        def is_mirror(a, b):
            if a is None or b is None:
                return a is b  # both must be missing
            return (a.val == b.val
                    and is_mirror(a.left, b.right)   # outer pair
                    and is_mirror(a.right, b.left))  # inner pair

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

JavaScript

var isSymmetric = function(root) {
  const isMirror = (a, b) => {
    if (!a || !b) return a === b; // both must be missing
    return a.val === b.val
      && isMirror(a.left, b.right)  // outer pair
      && isMirror(a.right, b.left); // inner pair
  };
  return root === null || isMirror(root.left, root.right);
};

What the interviewer is checking

It tests whether you can define a recursive relation between two trees, crossing left with right, and handle null cases cleanly before touching values.

Mistakes to avoid

• Comparing left with left and right with right, which checks equality, not mirroring.
• Checking only values level by level and missing differences in shape (nulls in different places).
• Accessing .val before confirming both nodes are non-null.

Follow-ups to expect

• Solve it iteratively. (Queue of node pairs.)
• How would you mirror (invert) a tree? (Swap children recursively.)
• Check whether two separate trees are identical. (Same recursion, no crossing.)

In real software

Mirror and equality checks on trees appear when diffing UI component trees, validating balanced layout structures, or comparing parsed expressions for structural equivalence.

Practice next