Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Symmetric Tree

EASYProblemSolveExternal Links

Description

Given the root of a binary tree, determine whether the tree is symmetric — that is, whether it is a mirror image of itself around its center.

A binary tree is symmetric if you could draw a vertical line through the root and the left half would be a perfect reflection of the right half. Specifically, for every node on the left side, there must be a corresponding node on the right side at the mirrored position with the same value.

Two binary trees side by side: one symmetric (mirror image) and one asymmetric, with a vertical dashed line through the root showing the mirror axis
Two binary trees side by side: one symmetric (mirror image) and one asymmetric, with a vertical dashed line through the root showing the mirror axis

Examples

Example 1

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

        1
       / \
      2   2
     / \ / \
    3  4 4  3

Output: true

Explanation: The left subtree has structure [2, 3, 4] and the right subtree has structure [2, 4, 3]. When you mirror the right subtree (swap all left and right children), it becomes [2, 3, 4] — identical to the left subtree. Every node on the left has a matching node at the mirrored position on the right with the same value.

Example 2

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

      1
     / \
    2   2
     \   \
      3   3

Output: false

Explanation: The left subtree's right child is 3, and the right subtree's right child is also 3. But for symmetry, the left subtree's right child should match the right subtree's LEFT child (which is null). The 3 on the right side is in the wrong mirrored position, so the tree is not symmetric.

Example 3

Input: root = [1]

  1

Output: true

Explanation: A single node with no children is trivially symmetric — there is nothing to mismatch.

Constraints

  • The number of nodes in the tree is in the range [1, 1000]
  • -100 ≤ Node.val ≤ 100

Editorial

Brute Force

Intuition

The most natural way to check symmetry is to think about what "mirror image" actually means. If you fold the tree along the root's vertical axis, the left subtree should land exactly on the right subtree.

More concretely, two subtrees are mirrors of each other if:

  1. Their root values are the same.
  2. The left child of the left subtree mirrors the right child of the right subtree.
  3. The right child of the left subtree mirrors the left child of the right subtree.

This is naturally recursive. Think of two people standing on opposite sides of a mirror — whatever the left person does with their left hand, the right person does with their right hand, and vice versa. We need to check every pair of "reflected" nodes.

The brute force approach uses a simple recursive helper function isMirror(left, right) that checks if two subtrees are mirror images.

Step-by-Step Explanation

Let's trace through Example 1:

        1
       / \
      2   2
     / \ / \
    3  4 4  3

Step 1: Start at root 1. Call isMirror(root.left=2, root.right=2).

Step 2: Compare the two nodes: left=2, right=2. Values match (2 == 2). Now check their children in mirrored order.

Step 3: Recursive call 1: isMirror(left.left=3, right.right=3). The outer children must match.

Step 4: Compare: left=3, right=3. Values match (3 == 3). Both have no children → both calls return true.

Step 5: Recursive call 2: isMirror(left.right=4, right.left=4). The inner children must match.

Step 6: Compare: left=4, right=4. Values match (4 == 4). Both have no children → both calls return true.

Step 7: Both recursive calls returned true, so isMirror(2, 2) returns true. The tree is symmetric.

Now let's verify Example 2 (asymmetric):

      1
     / \
    2   2
     \   \
      3   3

Step 8: Call isMirror(root.left=2, root.right=2). Values match.

Step 9: Recursive call 1: isMirror(left.left=null, right.right=3). Left is null but right is not → MISMATCH. Return false immediately.

Step 10: Since one recursive call returned false, the tree is NOT symmetric. Return false.

Recursive Mirror Check — Symmetric Tree Verification — Watch how the recursive function compares pairs of mirrored nodes, checking outer pairs and inner pairs at each level.

Algorithm

  1. If root is null, return true (empty tree is symmetric).
  2. Define a helper function isMirror(left, right):
    a. If both left and right are null, return true (matching empty subtrees).
    b. If only one is null, return false (structural mismatch).
    c. If left.val ≠ right.val, return false (value mismatch).
    d. Recursively check: isMirror(left.left, right.right) AND isMirror(left.right, right.left).
  3. Return isMirror(root.left, root.right).

Code

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isMirror(TreeNode* left, TreeNode* right) {
        // Both null means matching empty subtrees
        if (!left && !right) return true;
        // One null and one non-null means structural mismatch
        if (!left || !right) return false;
        // Values must match, and children must be mirrored
        return (left->val == right->val)
            && isMirror(left->left, right->right)
            && isMirror(left->right, right->left);
    }

    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return isMirror(root->left, root->right);
    }
};
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def isMirror(left, right):
            # Both None means matching empty subtrees
            if not left and not right:
                return True
            # One None and one non-None means structural mismatch
            if not left or not right:
                return False
            # Values must match, and children must be mirrored
            return (left.val == right.val
                    and isMirror(left.left, right.right)
                    and isMirror(left.right, right.left))

        if not root:
            return True
        return isMirror(root.left, root.right)
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

    private boolean isMirror(TreeNode left, TreeNode right) {
        // Both null means matching empty subtrees
        if (left == null && right == null) return true;
        // One null and one non-null means structural mismatch
        if (left == null || right == null) return false;
        // Values must match, and children must be mirrored
        return (left.val == right.val)
            && isMirror(left.left, right.right)
            && isMirror(left.right, right.left);
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each node at most once. At each node, we do O(1) work — compare values and make recursive calls. In the worst case (fully symmetric tree), we check all n nodes. If the tree is asymmetric, we may detect it early and short-circuit, but worst case is still O(n).

Space Complexity: O(h)

The recursion depth is the height of the tree. For a balanced tree this is O(log n), and for a completely skewed tree this is O(n). Since the problem constrains up to 1000 nodes, the maximum recursion depth is 1000, which is within typical stack limits but worth noting.

Why This Approach Is Not Efficient

The recursive approach is actually O(n) time and works well for this problem. However, it has a practical limitation: it uses the call stack, which has a fixed size. For very deep trees (height approaching n), the recursion can cause a stack overflow.

With up to 1000 nodes, a completely skewed tree would have height 1000, creating 1000 recursive calls. While most systems handle this, it is fragile — and the follow-up question specifically asks for an iterative solution.

The key insight is that we can replace the implicit recursion stack with an explicit data structure (a stack or queue) that we manage ourselves. This eliminates the risk of stack overflow and gives us more control over memory usage. The iterative approach uses the same mirror-comparison logic but processes node pairs using a stack instead of recursive calls.

Better Approach - Iterative with Stack

Intuition

Instead of using recursion, we simulate the same process with an explicit stack. We push pairs of nodes that should be mirrors of each other. Initially, we push (root.left, root.right). Then, at each step, we pop a pair, compare their values, and push their children in mirrored order:

  • Push (left.left, right.right) — outer children must match
  • Push (left.right, right.left) — inner children must match

If at any point a pair has mismatched values or one is null while the other isn't, the tree is not symmetric. If we process all pairs without finding a mismatch, the tree is symmetric.

This is exactly the same logic as recursion, but we manage the "to-do list" of pairs ourselves using a stack.

Step-by-Step Explanation

Let's trace through the asymmetric Example 2 to see how the stack detects the mismatch:

      1
     / \
    2   2
     \   \
      3   3

Step 1: Initialize stack with pair (root.left=2, root.right=2). Stack: [(2, 2)].

Step 2: Pop pair (2, 2). Both non-null, values match (2 == 2). Push children in mirror order:

  • Push (left.left=null, right.right=3) — outer children
  • Push (left.right=3, right.left=null) — inner children
  • Stack: [(null, 3), (3, null)].

Step 3: Pop pair (3, null). Left is non-null (3) but right is null. Structural mismatch detected! Return false immediately.

The tree is NOT symmetric. We detected the mismatch after checking only 2 pairs instead of visiting all nodes.

Now let's trace the symmetric Example 1:

        1
       / \
      2   2
     / \ / \
    3  4 4  3

Step 4: Stack starts with [(2, 2)].

Step 5: Pop (2, 2). Match. Push: (left.left=3, right.right=3) and (left.right=4, right.left=4). Stack: [(3, 3), (4, 4)].

Step 6: Pop (4, 4). Match. Both are leaves. Push: (null, null) and (null, null). Stack: [(3, 3), (null, null), (null, null)].

Step 7: Pop (null, null). Both null → skip, continue. Stack: [(3, 3), (null, null)].

Step 8: Pop (null, null). Both null → skip. Stack: [(3, 3)].

Step 9: Pop (3, 3). Match. Both are leaves. Push null pairs. All get skipped.

Step 10: Stack is empty. All pairs matched. Return true.

Iterative Stack — Mirror Pair Comparison — Watch how pairs of nodes are pushed and popped from the stack. Each pair represents two nodes that should be mirrors. A mismatch means the tree is asymmetric.

Algorithm

  1. If root is null, return true.
  2. Initialize a stack and push the pair (root.left, root.right).
  3. While the stack is not empty:
    a. Pop a pair (node1, node2).
    b. If both are null, continue (skip this pair).
    c. If one is null and the other isn't, return false.
    d. If node1.val ≠ node2.val, return false.
    e. Push (node1.left, node2.right) — outer children pair.
    f. Push (node1.right, node2.left) — inner children pair.
  4. If the stack empties without mismatches, return true.

Code

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;

        stack<pair<TreeNode*, TreeNode*>> st;
        st.push({root->left, root->right});

        while (!st.empty()) {
            auto [left, right] = st.top();
            st.pop();

            // Both null — this pair is fine
            if (!left && !right) continue;
            // One null, other not — structural mismatch
            if (!left || !right) return false;
            // Value mismatch
            if (left->val != right->val) return false;

            // Push children in mirror order
            st.push({left->left, right->right});   // outer pair
            st.push({left->right, right->left});    // inner pair
        }

        return true;
    }
};
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True

        stack = [(root.left, root.right)]

        while stack:
            left, right = stack.pop()

            # Both None — this pair is fine
            if not left and not right:
                continue
            # One None, other not — structural mismatch
            if not left or not right:
                return False
            # Value mismatch
            if left.val != right.val:
                return False

            # Push children in mirror order
            stack.append((left.left, right.right))   # outer pair
            stack.append((left.right, right.left))    # inner pair

        return True
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        Deque<TreeNode[]> stack = new ArrayDeque<>();
        stack.push(new TreeNode[]{root.left, root.right});

        while (!stack.isEmpty()) {
            TreeNode[] pair = stack.pop();
            TreeNode left = pair[0];
            TreeNode right = pair[1];

            // Both null — this pair is fine
            if (left == null && right == null) continue;
            // One null, other not — structural mismatch
            if (left == null || right == null) return false;
            // Value mismatch
            if (left.val != right.val) return false;

            // Push children in mirror order
            stack.push(new TreeNode[]{left.left, right.right});   // outer pair
            stack.push(new TreeNode[]{left.right, right.left});    // inner pair
        }

        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

We process each node at most once (as part of a pair). Each pair comparison is O(1). In the worst case we check all n/2 pairs (roughly n nodes), giving O(n) total time. Early termination on asymmetric trees can make it faster in practice.

Space Complexity: O(n)

In the worst case, the stack can hold up to n/2 pairs. For a complete binary tree, the last level has roughly n/2 nodes, so before processing any leaf pairs, the stack could hold O(n) entries. This is technically O(n) space, compared to O(h) for recursion on balanced trees, but it avoids call stack overflow risks.

Why This Approach Is Not Efficient

The iterative stack approach is already O(n) time, which is optimal since we must examine every node. However, it processes pairs in a depth-first order because it uses a stack (LIFO). This means it explores one branch fully before checking the other.

A queue-based approach processes pairs in breadth-first (level-by-level) order. This can be more intuitive for symmetry checking because symmetry is inherently a level-by-level property — at each level, the nodes should be a palindrome. Using a queue also gives a slightly different traversal pattern that mirrors how humans naturally verify symmetry: checking one level at a time from top to bottom.

Both approaches have the same time and space complexity, but the queue-based approach provides a natural level-order perspective.

Optimal Approach - Iterative with Queue

Intuition

Instead of a stack, we use a queue to process mirror pairs in level order — breadth-first. The logic is identical to the stack approach: enqueue pairs that should be mirrors, dequeue and compare, enqueue their children in mirrored order.

The key difference is traversal order. With a queue (FIFO), we check all pairs at one level before moving to the next. This mirrors how our eyes naturally scan for symmetry: we look at the top of a shape first, then scan downward level by level.

For symmetric trees, this processes the same pairs in a slightly different order. For asymmetric trees, it may detect mismatches at shallower levels first (which is often where mismatches occur), potentially checking fewer total pairs.

Step-by-Step Explanation

Let's trace through Example 1 (symmetric tree) using a queue:

        1
       / \
      2   2
     / \ / \
    3  4 4  3

Step 1: Initialize queue with pair (root.left=2, root.right=2). Queue: [(2, 2)].

Step 2: Dequeue pair (2, 2). Both non-null, values match. Enqueue children in mirror order:

  • Enqueue (left.left=3, right.right=3) — outer pair
  • Enqueue (left.right=4, right.left=4) — inner pair
  • Queue: [(3, 3), (4, 4)].

Step 3: Dequeue pair (3, 3). Both non-null, values match (3 == 3). Both are leaves. Enqueue their null children:

  • Enqueue (null, null) and (null, null).
  • Queue: [(4, 4), (null, null), (null, null)].

Step 4: Dequeue pair (4, 4). Both non-null, values match (4 == 4). Both are leaves. Enqueue null pairs.

  • Queue: [(null, null), (null, null), (null, null), (null, null)].

Step 5: Dequeue (null, null). Both null → skip. Continue.

Step 6: Dequeue (null, null). Both null → skip. Continue.

Step 7: Dequeue (null, null). Both null → skip. Continue.

Step 8: Dequeue (null, null). Both null → skip. Queue is empty.

Step 9: All pairs checked without mismatch. Return true.

Queue-Based Level-Order Symmetry Check — Watch how mirror pairs are enqueued and dequeued level by level. The queue ensures we verify symmetry from the top of the tree downward.

Algorithm

  1. If root is null, return true.
  2. Initialize a queue and enqueue the pair (root.left, root.right).
  3. While the queue is not empty:
    a. Dequeue a pair (node1, node2).
    b. If both are null, continue.
    c. If one is null and the other isn't, return false.
    d. If node1.val ≠ node2.val, return false.
    e. Enqueue (node1.left, node2.right) — outer children pair.
    f. Enqueue (node1.right, node2.left) — inner children pair.
  4. If the queue empties without mismatches, return true.

Code

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;

        queue<pair<TreeNode*, TreeNode*>> q;
        q.push({root->left, root->right});

        while (!q.empty()) {
            auto [left, right] = q.front();
            q.pop();

            // Both null — matching empty subtrees
            if (!left && !right) continue;
            // One null, other not — structural mismatch
            if (!left || !right) return false;
            // Value mismatch
            if (left->val != right->val) return false;

            // Enqueue children in mirror order
            q.push({left->left, right->right});   // outer pair
            q.push({left->right, right->left});    // inner pair
        }

        return true;
    }
};
from collections import deque

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True

        queue = deque([(root.left, root.right)])

        while queue:
            left, right = queue.popleft()

            # Both None — matching empty subtrees
            if not left and not right:
                continue
            # One None, other not — structural mismatch
            if not left or not right:
                return False
            # Value mismatch
            if left.val != right.val:
                return False

            # Enqueue children in mirror order
            queue.append((left.left, right.right))   # outer pair
            queue.append((left.right, right.left))    # inner pair

        return True
import java.util.*;

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        Queue<TreeNode[]> queue = new LinkedList<>();
        queue.offer(new TreeNode[]{root.left, root.right});

        while (!queue.isEmpty()) {
            TreeNode[] pair = queue.poll();
            TreeNode left = pair[0];
            TreeNode right = pair[1];

            // Both null — matching empty subtrees
            if (left == null && right == null) continue;
            // One null, other not — structural mismatch
            if (left == null || right == null) return false;
            // Value mismatch
            if (left.val != right.val) return false;

            // Enqueue children in mirror order
            queue.offer(new TreeNode[]{left.left, right.right});   // outer pair
            queue.offer(new TreeNode[]{left.right, right.left});    // inner pair
        }

        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

Every node is processed exactly once as part of a mirror pair. Each comparison is O(1). Total: O(n) time. Same as the recursive and stack approaches — this is optimal since we must inspect every node to confirm symmetry.

Space Complexity: O(n)

In the worst case (a complete binary tree), the queue can hold up to O(n/2) pairs at the widest level. For a tree with 1000 nodes, this is at most about 500 pairs. The queue-based approach uses O(n) space in the worst case, same as the stack approach. Both iterative methods avoid call stack overflow risks that the recursive approach faces with deep trees.

Comparison of all three approaches:

ApproachTimeSpaceStack-safe?Traversal Order
RecursiveO(n)O(h)No (deep trees risk overflow)Depth-first
Iterative StackO(n)O(n)YesDepth-first
Iterative QueueO(n)O(n)YesBreadth-first (level-order)