Symmetric Tree

Difficulty: Easy

Problem

Decide whether the binary tree rooted at root is a mirror image of itself. Picture a vertical mirror through the root: the tree is symmetric exactly when the left side is the reflection of the right side, matching in both shape and node values. Return true if it is, false otherwise.

Example

Input: root = [1,2,2,3,4,4,3]
Output: true
Explanation: The left subtree and the right subtree are mirror images of each other: the 2s face each other, the outer 3s match, and the inner 4s match. Fold the tree down the middle and every node lands on a partner with the same value.

Brute-force approach

The first idea is the one in the lesson: flip the left half (Invert Binary Tree), then run Same Tree against the right half. It is correct, but it needs a copy or changes the tree, and it makes more calls: 14 calls against 7 on [1,2,2,3,4,4,3] (7 for the flip and 7 for the comparison). The crossed walk compares the halves as if one were flipped, with no flip at all.

Steps

  1. Flip the left half of the tree (invert it)
  2. Run Same Tree on the flipped left half and the right half
  3. Return the result

Time complexity: O(n) · Space complexity: O(n) for a copy of the half, or a changed input tree

Trade-offs

  • Two passes: 14 calls against 7 on the example
  • Either changes the tree (a read-only question edits its input) or needs a copy of the half

Optimal approach

Key insight: Same Tree compared straight pairs; Symmetric Tree compares CROSSED pairs. One crossing turns 'equal' into 'mirrored'.

Compare the left and right halves of the tree in lock-step, exactly like Same Tree, but walk them in OPPOSITE directions. Each mirror(a, b) call runs the familiar three checks, then recurses into the CROSSED children: the outer pair and the inner pair.

Steps

  1. Define a helper mirror(a, b): are the subtrees at a and b mirror images of each other?
  2. If a and b are both null, return true, two empty spots mirror perfectly
  3. If exactly one of them is null, or their values differ, return false
  4. Recurse CROSSED: mirror(a.left, b.right) AND mirror(a.right, b.left)
  5. Kick everything off with mirror(root.left, root.right), the root always matches itself

Time complexity: O(n) · Space complexity: O(h): O(log n) when balanced, up to about n / 2 deep (so O(n)) for two mirrored chains; a skewed tree is cheap

Pseudocode

function isSymmetric(root):
    if root is null:
        return ____
    function mirror(a, b):
        if a is null and b is null:
            return true
        if a is null or b is null:
            return false
        if a.val != b.val:
            return false
        
        return mirror(a.left, ____) and
               mirror(a.right, ____)
    
    return mirror(root.____, root.____)

Hints

  • The three checks at the top are copied from Same Tree unchanged. Every blank lives in the pairing, not the checks.
  • Picture the mirror: a's LEFT child must line up with b's ___ child. (Your left hand, the reflection's right hand.)
  • Two crossed pairs: the outer pair is (a.left, b.right) and the inner pair is (a.right, b.left). Each call reaches to the OPPOSITE side of b.
  • The root sits on the fold line and always matches itself, so the very first pair to compare is its two children.
  • Edge case first: an empty tree (root is null) is symmetric, so return true before reading root.left.
  • A mirror swaps left and right, so a.left meets b.RIGHT (and a.right meets b.left): never left with left.
  • A level can read the same backwards while the shape differs: [1,2,2,null,3,null,3] has 2, 2 then 3, 3 but both 3s hang on the RIGHT, so it is not symmetric.

Complexity questions

What is the time complexity of isSymmetric on a tree with n nodes?

O(n). Every node lands in exactly one mirror pair, and each pair costs O(1): two null checks and one value comparison. Checking all the pairs therefore touches every node once, O(n). Exactly: at most n calls, and exactly n calls on a symmetric tree (every node except the root is in one pair, and a pair makes two calls).

What is the space complexity of the recursive solution?

O(h): the recursion call stack, where h is the tree height (up to about n / 2 pairs waiting). We allocate nothing ourselves, but recursion isn't free: the call stack holds one pair per level as the two walkers descend together. That's O(h): O(log n) for a balanced tree. A completely skewed tree is cheap, not the worst case: it returns false at its very first comparison, with one pair waiting. The true worst case is a symmetric tree made of two long mirrored chains (an A shape), with about n / 2 pairs waiting (n = 7: 4 pairs; n = 101: 51), so O(n).

Could you solve this by INVERTING the left subtree, then running Same Tree against the right subtree?

Yes! A valid composition of the two previous lessons: one extra traversal, still O(n). A tree is symmetric exactly when invert(root.left) is the SAME tree as root.right, inverting turns 'mirrored' into 'equal'. Invert is O(n) and Same Tree is O(n), so the combo stays O(n), just with one extra traversal (and it mutates the tree). The crossed recursion does it in a single pass, but spotting this composition means you truly own all three lessons.

In the iterative version (a queue or an explicit stack instead of recursion), what does each entry hold?

PAIRS of nodes that must mirror each other. The unit of work is always a PAIR (a, b). Pop a pair, run the three checks, then push the two crossed pairs: (a.left, b.right) and (a.right, b.left). The recursive version's call stack was holding pairs all along. The iterative version just makes that explicit.

Check your understanding of Symmetric Tree

What does 'symmetric' actually mean for a binary tree?

The left half is the MIRROR image of the right half. Careful: 'exact copy' is Same-Tree thinking! Symmetric means the right half is the left half flipped left↔right, like a reflection. A tree can be balanced or full of equal values and still not be a mirror of itself.

Is the tree [1,2,2,null,3,null,3] symmetric?

No: both 3s hang on the RIGHT side of their parents; a mirror needs them on OPPOSITE sides. The two subtrees ARE identical (each is a 2 with a right child 3). Same Tree would happily say true! But fold the tree down the middle: the left 3 needs its partner on the LEFT side of the right subtree, and that spot is null. Identical is not the same as mirrored.

To check mirror(a, b), which children pair up in the recursive calls?

a.left with b.RIGHT, and a.right with b.LEFT, the crossing IS the mirror. The pairs cross: a's left child must mirror b's right child, and a's right child must mirror b's left child. Pairing a.left with b.left would check that the subtrees are EQUAL: that's Same Tree, not a mirror.

Where does the mirror comparison start?

mirror(root.left, root.right). The root sits ON the mirror line and always matches itself. The fold line passes straight through the root, so the root is its own reflection. It can never break the symmetry. The first pair that actually needs checking is the root's two children: mirror(root.left, root.right).

Stand in front of a mirror and raise your LEFT hand. Which hand does your reflection raise?

Its RIGHT hand, and that's exactly why the recursion crosses. A mirror swaps left and right (never up and down). Your left hand lines up with the reflection's right hand. Which is precisely why mirror(a, b) pairs a.left with b.right instead of a.left with b.left.

Related problems

Keep practising