Symmetric Tree

Easy Trees & BST Recursion Original on LeetCode

Symmetric Tree is a easy trees & bst problem solved with the recursion pattern. The best approach, recursive mirror check, runs in O(n) time and O(h) space. Below are 2 approaches in Java, from iterative (queue of mirrored pairs) up.

Problem

Decide whether a binary tree is a mirror image of itself around its centre.

Examples

Example 1

Input: root = [1, 2, 2, 3, 4, 4, 3]
Output: true

Example 2

Input: root = [1, 2, 2, null, 3, null, 3]
Output: false

Constraints

The tree has 1 to 1000 nodes.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Iterative (queue of mirrored pairs)	`O(n)`	`O(n)`
Recursive mirror check	`O(n)`	`O(h)`

1Iterative (queue of mirrored pairs)

TimeO(n)

SpaceO(n)

Push (left, right) and check pairs; for each matching pair enqueue (a.left, b.right) and (a.right, b.left).

Queue the pair (root.left, root.right) and check pairs as in Same Tree, but crossed.

Java

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode[]> dq = new ArrayDeque<>();
        dq.add(new TreeNode[] { root.left, root.right });
        while (!dq.isEmpty()) {
            TreeNode[] p = dq.poll();
            TreeNode a = p[0], b = p[1];
            if (a == null && b == null) continue;
            if (a == null || b == null || a.val != b.val) return false;
            dq.add(new TreeNode[] { a.left, b.right });
            dq.add(new TreeNode[] { a.right, b.left });
        }
        return true;
    }
}

2Recursive mirror check

TimeO(n)

SpaceO(h)

Two subtrees mirror each other when their roots match, the left's left mirrors the right's right, and the left's right mirrors the right's left.

mirror(a, b): if a == null || b == null, return a == b.
return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left).

Java

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return mirror(root.left, root.right);
    }

    private boolean mirror(TreeNode a, TreeNode b) {
        if (a == null || b == null) return a == b;
        return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
    }
}

Edge cases to test

Single node (true)
Equal values but mirrored shape broken

Hints

Hint 1

Compare the left subtree with the right subtree, pairing outer with outer and inner with inner.

FAQ

What is the best time complexity for Symmetric Tree?

Recursive mirror check runs in O(n) time and O(h) extra space.

Which pattern does Symmetric Tree use?

It is a trees & bst problem that uses the recursion pattern. Other problems with the same pattern: Binary Tree Inorder Traversal (Recursive), Binary Tree Preorder Traversal (Recursive), Binary Tree Postorder Traversal (Recursive).

Is there a brute force solution for Symmetric Tree?

Yes. Iterative (queue of mirrored pairs) takes O(n) time and O(n) space. Push (left, right) and check pairs; for each matching pair enqueue (a.left, b.right) and (a.right, b.left).

Which edge cases should I test for Symmetric Tree?

Single node (true); Equal values but mirrored shape broken.