Is the Tree a Mirror Image of Itself

Easy15–20 min

Topics

Binary TreeDFSRecursionSymmetry

Companies

AmazonMicrosoftGoogleLinkedIn

You are given the root of a binary tree. Decide whether the tree is a mirror image of itself: if you flipped the left subtree left-to-right, it would have to be exactly the same as the right subtree — same shape, same values. An empty tree counts as a mirror.

Building a flipped copy and comparing works, but the flip and the comparison can be combined: walk the two subtrees together, always pairing the outer children with each other and the inner children with each other.

Test Case 1:

Input:root = [8, 4, 4, null, 6, 6]

Output:true

Explanation:Below the root, both children hold 4. The left 4 has a child 6 on its right; the right 4 has a child 6 on its left — exactly the mirror position.

Test Case 2:

Input:root = [6, 3, 3, 9, null, 9]

Output:false

Explanation:Both 3s have a child 9, but on the same side: the 9 under the left 3 is on its left, and so is the 9 under the right 3. In a mirror it would have to be on the right.

Test Case 3:

Input:root = []

Output:true

Explanation:An empty tree is trivially symmetric.

Constraints

◆0 ≤ number of nodes ≤ 100
◆−100 ≤ node.val ≤ 100
◆The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child
◆The tree is a mirror image of itself when its left subtree, flipped left-to-right, is exactly the same as its right subtree (same shape and same values). Return true or false; an empty tree counts as a mirror

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Build the Flipped Left Subtree, Then Compare

Brute

Follow the definition literally. Build a flipped copy of the root's left subtree — for every node in the copy, its left child is the flipped copy of the original's right child and vice versa. Then check whether that flipped copy is exactly the same tree as the root's right subtree, comparing shape and values node by node. It is correct and easy to reason about, but it allocates a whole new subtree (O(n) extra space) before the comparison even begins.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public boolean isMirror(TreeNode root) {
        if (root == null) return true;
        return same(mirrorCopy(root.left), root.right);
    }

    private TreeNode mirrorCopy(TreeNode node) {
        if (node == null) return null;
        TreeNode copy = new TreeNode(node.val);
        copy.left = mirrorCopy(node.right);
        copy.right = mirrorCopy(node.left);
        return copy;
    }

    private boolean same(TreeNode x, TreeNode y) {
        if (x == null && y == null) return true;
        if (x == null || y == null) return false;
        return x.val == y.val && same(x.left, y.left) && same(x.right, y.right);
    }
}

Optimal — Compare Mirror Positions in One Pass

Optimal

Skip the copy. Walk the left and right subtrees at the same time with a helper that takes two nodes, a and b, that should be mirror images. Both missing → fine. Only one missing → not a mirror. Otherwise their values must be equal, and the mirror rule pairs the OUTER children (a's left with b's right) and the INNER children (a's right with b's left). All three conditions joined with && short-circuit at the first mismatch. No copy is built: O(n) time in the worst case, O(h) extra space for the recursion.