Course4all
Join us on telegram
Home/dsa/Trees/Symmetric Tree

Symmetric Tree

Master this topic with zero to advance depth.

Symmetric Tree

Check if a tree is a mirror of itself.

Easy

Examples

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

Level I: Recursive DFS

Intuition

A tree is symmetric if its left and right subtrees are mirrors of each other. Two trees t1 and t2 are mirrors if:

  1. Their roots have the same value.
  2. t1.left is a mirror of t2.right.
  3. t1.right is a mirror of t2.left.
⏱ O(N)💾 O(H)

Detailed Dry Run

Mirror(L, R) -> L.val == R.val && Mirror(L.left, R.right) && Mirror(L.right, R.left).

java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }
    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null || t1.val != t2.val) return false;
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }
}
Approach 2

Level II: Iterative BFS (Queue)

Intuition

Use a queue to process nodes in pairs. Each pair contains nodes that should be mirrors of each other. For a root, we push (root.left, root.right).

Diagram

(1) Queue: [1.L, 1.R] -> [2, 2] (2) Pop pair (2, 2), Push pairs: [(2.L, 2.R), (2.R, 2.L)] -> [3, 3, 4, 4]
⏱ O(N)💾 O(W)

Detailed Dry Run

Queue: [2, 2]. Pop 2, 2. Push 3(L), 3(R) and 4(R), 4(L). Queue: [3, 3, 4, 4]. All match -> true.

java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root.left); q.add(root.right);
        while (!q.isEmpty()) {
            TreeNode t1 = q.poll(), t2 = q.poll();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null || t1.val != t2.val) return false;
            q.add(t1.left); q.add(t2.right);
            q.add(t1.right); q.add(t2.left);
        }
        return true;
    }
}
Approach 3

Level III: Iterative DFS (Two Stacks)

Intuition

Process the tree in parallel using two stacks. One stack follows Left -> Right and the other follows Right -> Left. Their values and structure must match at every step.

⏱ O(N)💾 O(H)

Detailed Dry Run

Stack1: [L], Stack2: [R]. Pop both, compare. Push L1.left, R1.right and L1.right, R1.left to respective stacks.

java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> s1 = new Stack<>(), s2 = new Stack<>();
        s1.push(root.left); s2.push(root.right);
        while (!s1.isEmpty()) {
            TreeNode n1 = s1.pop(), n2 = s2.pop();
            if (n1 == null && n2 == null) continue;
            if (n1 == null || n2 == null || n1.val != n2.val) return false;
            s1.push(n1.left); s2.push(n2.right);
            s1.push(n1.right); s2.push(n2.left);
        }
        return true;
    }
}
← Previous QuestionSame Tree
Next Question →Subtree of Another Tree