Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Symmetric Tree solution and explanation

EasyBinary TreeBreadth-First SearchDepth-First SearchTree6 min read62.1% acceptanceUpdated 9 Apr 2026
Asked atMetaLinkedInVKAmazonMicrosoftBloomberg
+5 moreYandexGoogleTiktokAppleGoldman Sachs
Practise Symmetric Tree
6:40
Symmetric Tree - Leetcode 101 - PythonNeetCodeIO · 6:40 · 66K viewsWatch on YouTube
9 more videos on this problem
  1. Symmetric Tree - Leetcode 101 - PythonNeetCodeIO · 6:40 · 66K views
  2. LeetCode Symmetric Tree Solution Explained - JavaNick White · 4:04 · 45K views
  3. Symmetric Tree (Leetcode - 101) - (Amazon, Microsoft, Mentor (Siemens)) : Explanation ➕ Live CodingcodestorywithMIK · 10:07 · 12K views
  4. Symmetric Tree - Leetcode 101 - Trees (Python)Greg Hogg · 4:16 · 9K views
  5. Symmetric Tree (LeetCode 101) | Full Iterative solution with animations diagrams | BFSNikhil Lohia · 17:21 · 7K views
  6. Solving LeetCode 101 in JavaScript (Symmetric Tree)KA Education · 5:56 · 3K views
  7. [Java] Leetcode 101. Symmetric Tree [Binary Tree #6]Eric Programming · 6:52 · 1K views
  8. Symmetric Tree - LeetCode 101 - JavaScriptAlgoJS · 4:06 · 1K views
  9. Symmetric Tree | LeetCode 101 | EasyCode And Coffee · 6:58 · 1K views
  10. Symmetric Tree - Leetcode 101 - PythonTechError · 7:52 · 712 views

The problem

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

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 number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?

Approach overview

Problem Overview: Given the root of a binary tree, determine whether the tree is symmetric around its center. A tree is symmetric if the left subtree is a mirror reflection of the right subtree — every node on the left must match the corresponding node on the right in value and position.

This problem is fundamentally about comparing two subtrees for mirror equality. Instead of checking a subtree against itself, you compare the left child of one subtree with the right child of the other. The pattern naturally fits recursive tree traversal or an iterative queue-based comparison.

Approach 1: Recursive Mirror Check (DFS) (Time: O(n), Space: O(h))

The recursive solution directly models the mirror definition. You write a helper function that compares two nodes. If both nodes are null, the structure matches. If only one is null or the values differ, the tree is not symmetric. Otherwise, recursively compare left.left with right.right and left.right with right.left.

This traversal touches each node exactly once, giving O(n) time complexity. The recursion depth equals the tree height, so space complexity is O(h) due to the call stack. This approach is clean and closely follows the mirror definition of symmetry, making it easy to reason about in interviews. It relies on concepts from Depth-First Search and Binary Tree recursion patterns.

Approach 2: Iterative Mirror Check (BFS with Queue) (Time: O(n), Space: O(n))

The iterative approach simulates the mirror comparison using a queue. Start by pushing the root's left and right children. While the queue is not empty, pop two nodes at a time. If both are null, continue. If only one is null or their values differ, the tree is not symmetric.

If the values match, enqueue their children in mirror order: (left.left, right.right) and (left.right, right.left). This ensures that nodes that should mirror each other are always compared together. Every node is processed once, resulting in O(n) time complexity. The queue may hold up to a full tree level, so the worst‑case space complexity is O(n). This approach mirrors a level-order traversal using Breadth-First Search.

Recommended for interviews: The recursive DFS solution is the most common answer because it directly encodes the mirror definition and requires minimal code. Interviewers often expect this approach first. The iterative queue solution is equally efficient and demonstrates that you understand both DFS and BFS traversal patterns in a Tree. Mentioning both approaches shows deeper understanding of traversal strategies.

Approach 1: Recursive Approach

This approach uses recursion to compare the left subtree and right subtree of the binary tree. For two trees to be mirror images, the following three conditions must be true:

  • Their two roots have the same value.
  • The right subtree of each tree is a mirror reflection of the left subtree of the other tree.
  • Both subtrees must themselves be mirror images.

Recursion is an elegant way to check this condition for each node in the tree.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.isMirror(root, root)
    
    def isMirror(self, t1: TreeNode, t2: TreeNode) -> bool:
        if t1 is None and t2 is None:
            return True
        if t1 is None or t2 is None:
            return False
        return (t1.val == t2.val and
                self.isMirror(t1.right, t2.left) and
                self.isMirror(t1.left, t2.right))
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public 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) return false;
        return (t1.val == t2.val) &&
               isMirror(t1.right, t2.left) &&
               isMirror(t1.left, t2.right);
    }
}
#include <iostream>
using namespace std;

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

class Solution {
public:
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (!t1 && !t2) return true;
        if (!t1 || !t2) return false;
        return (t1->val == t2->val) &&
               isMirror(t1->right, t2->left) &&
               isMirror(t1->left, t2->right);
    }
    bool isSymmetric(TreeNode* root) {
        return isMirror(root, root);
    }
};
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var isSymmetric = function(root) {
    return isMirror(root, root);
};

function isMirror(t1, t2) {
    if (!t1 && !t2) return true;
    if (!t1 || !t2) return false;
    return (t1.val === t2.val) &&
           isMirror(t1.right, t2.left) &&
           isMirror(t1.left, t2.right);
}
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

bool isMirror(struct TreeNode* t1, struct TreeNode* t2) {
    if (t1 == NULL && t2 == NULL) return true;
    if (t1 == NULL || t2 == NULL) return false;
    return (t1->val == t2->val) && 
           isMirror(t1->right, t2->left) &&
           isMirror(t1->left, t2->right);
}

bool isSymmetric(struct TreeNode* root) {
    return isMirror(root, root);
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public bool IsSymmetric(TreeNode root) {
        return IsMirror(root, root);
    }

    private bool IsMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val) &&
               IsMirror(t1.right, t2.left) &&
               IsMirror(t1.left, t2.right);
    }
}

In this Python code, a Solution class contains a public method isSymmetric and a private helper method isMirror. isMirror checks whether two subtrees are mirror images of each other recursively.

Complexity

Time Complexity: O(n), where n denotes the node count.
Space Complexity: O(h), stemming from the recursion stack where h is the tree's height.

Try this approach in the editor

Approach 2: Iterative Approach

This approach utilizes a queue data structure to iteratively compare nodes in the binary tree. It behaves like the recursive method mirroring trees, but it exchanges recursion for a loop that dequeues two nodes at a time.

  • If both nodes are null, proceed to the next iteration.
  • If only one is null, return false as they aren't mirrors.
  • If their values diverge, return false as well.
  • Insert the children of these nodes in the reverse order to continue the symmetry check in subsequent iterations.
from collections import deque

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        q = deque([root, root])
        while q:
            t1 = q.popleft()
            t2 = q.popleft()
            if not t1 and not t2:
                continue
            if not t1 or not t2:
                return False
            if t1.val != t2.val:
                return False
            q.append(t1.left)
            q.append(t2.right)
            q.append(t1.right)
            q.append(t2.left)
        return True
import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;
            queue.add(t1.left);
            queue.add(t2.right);
            queue.add(t1.right);
            queue.add(t2.left);
        }
        return true;
    }
}
#include <iostream>
#include <queue>
using namespace std;

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

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode*> q;
        q.push(root);
        q.push(root);
        while (!q.empty()) {
            TreeNode* t1 = q.front(); q.pop();
            TreeNode* t2 = q.front(); q.pop();
            if (!t1 && !t2) continue;
            if (!t1 || !t2) return false;
            if (t1->val != t2->val) return false;
            q.push(t1->left);
            q.push(t2->right);
            q.push(t1->right);
            q.push(t2->left);
        }
        return true;
    }
};
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var isSymmetric = function(root) {
    if (!root) return true;
    let queue = [];
    queue.push(root);
    queue.push(root);
    while (queue.length > 0) {
        let t1 = queue.shift();
        let t2 = queue.shift();
        if (!t1 && !t2) continue;
        if (!t1 || !t2) return false;
        if (t1.val !== t2.val) return false;
        queue.push(t1.left);
        queue.push(t2.right);
        queue.push(t1.right);
        queue.push(t2.left);
    }
    return true;
}
#include <stdbool.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

typedef struct TreeNode* QueueNode;
typedef struct {
    QueueNode* data;
    int front, rear, size, capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->data = (QueueNode*)malloc(queue->capacity * sizeof(QueueNode));
    return queue;
}

bool isFull(Queue* queue) { return queue->size == queue->capacity; }
bool isEmpty(Queue* queue) { return queue->size == 0; }

void enqueue(Queue* queue, QueueNode item) {
    if (isFull(queue)) return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->data[queue->rear] = item;
    queue->size++;
}

QueueNode dequeue(Queue* queue) {
    if (isEmpty(queue)) return NULL;
    QueueNode item = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;
    return item;
}

bool isSymmetric(struct TreeNode* root) {
    if (!root) return true;
    Queue* queue = createQueue(1000);
    enqueue(queue, root);
    enqueue(queue, root);
    while (!isEmpty(queue)) {
        struct TreeNode* t1 = dequeue(queue);
        struct TreeNode* t2 = dequeue(queue);
        if (!t1 && !t2) continue;
        if (!t1 || !t2) return false;
        if (t1->val != t2->val) return false;
        enqueue(queue, t1->left);
        enqueue(queue, t2->right);
        enqueue(queue, t1->right);
        enqueue(queue, t2->left);
    }
    return true;
}
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public bool IsSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        queue.Enqueue(root);
        while (queue.Count != 0) {
            TreeNode t1 = queue.Dequeue();
            TreeNode t2 = queue.Dequeue();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;
            queue.Enqueue(t1.left);
            queue.Enqueue(t2.right);
            queue.Enqueue(t1.right);
            queue.Enqueue(t2.left);
        }
        return true;
    }
}

This Python implementation of the iterative method efficiently uses a deque from the collections module for dequeueing operations. Nodes are enqueued in pairs, and each is checked for symmetry before the process continues.

Complexity

Time Complexity: O(n), n denoting the number of nodes processed.
Space Complexity: O(n), predicated on storing node references in deque.

Try this approach in the editor

Approach 3: Recursion

We design a function dfs(root1, root2) to determine whether two binary trees are symmetric. The answer is dfs(root.left, root.right).

The logic of the function dfs(root1, root2) is as follows:

  • If both root1 and root2 are null, the two binary trees are symmetric, and we return true;
  • If only one of root1 and root2 is null, or root1.val neq root2.val, we return false;
  • Otherwise, we check whether the left subtree of root1 is symmetric with the right subtree of root2, and whether the right subtree of root1 is symmetric with the left subtree of root2, using recursion.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isSymmetric(root: TreeNode | null): boolean {
    const dfs = (root1: TreeNode | null, root2: TreeNode | null): boolean => {
        if (root1 === root2) {
            return true;
        }
        if (!root1 || !root2 || root1.val !== root2.val) {
            return false;
        }
        return dfs(root1.left, root2.right) && dfs(root1.right, root2.left);
    };
    return dfs(root.left, root.right);
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
	var dfs func(root1, root2 *TreeNode) bool
	dfs = func(root1, root2 *TreeNode) bool {
		if root1 == root2 {
			return true
		}
		if root1 == nil || root2 == nil || root1.Val != root2.Val {
			return false
		}
		return dfs(root1.Left, root2.Right) && dfs(root1.Right, root2.Left)
	}
	return dfs(root.Left, root.Right)
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn dfs(root1: Option<Rc<RefCell<TreeNode>>>, root2: Option<Rc<RefCell<TreeNode>>>) -> bool {
            match (root1, root2) {
                (Some(node1), Some(node2)) => {
                    let node1 = node1.borrow();
                    let node2 = node2.borrow();
                    node1.val == node2.val
                        && dfs(node1.left.clone(), node2.right.clone())
                        && dfs(node1.right.clone(), node2.left.clone())
                }
                (None, None) => true,
                _ => false,
            }
        }

        match root {
            Some(root) => dfs(root.borrow().left.clone(), root.borrow().right.clone()),
            None => true,
        }
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Approach

Time Complexity: O(n), where n denotes the node count.
Space Complexity: O(h), stemming from the recursion stack where h is the tree's height.

Iterative Approach

Time Complexity: O(n), n denoting the number of nodes processed.
Space Complexity: O(n), predicated on storing node references in deque.

Recursion–

Complexity analysis

ApproachTimeSpaceWhen to Use
Recursive Mirror Check (DFS)O(n)O(h)Best for interviews and clean implementations when recursion depth is manageable
Iterative Mirror Check (BFS Queue)O(n)O(n)Useful when avoiding recursion or when implementing level-order style traversal

Frequently asked questions

Is Symmetric Tree easy or hard?

Symmetric Tree is categorized as an Easy problem on most coding platforms with an acceptance rate around 60%. The challenge lies in recognizing the mirror comparison pattern rather than performing a standard traversal.

Symmetric Tree Python/Java solution

In Python or Java, the typical solution defines a helper function that recursively compares two nodes. The function checks value equality and recursively validates mirrored children. Both languages implement the same O(n) DFS logic with recursion.

How to solve Symmetric Tree in O(n)?

Traverse the tree while comparing nodes in mirrored positions. In the recursive solution, compare left.left with right.right and left.right with right.left at every step. Each node pair is processed once, giving O(n) time complexity with O(h) auxiliary space for recursion.

What is the best approach for Symmetric Tree?

The recursive mirror check using Depth-First Search is the most common solution. It compares two subtrees at a time and ensures the left subtree mirrors the right subtree. The algorithm runs in O(n) time because every node is visited once, and it uses O(h) space from the recursion stack where h is the tree height.

Is Symmetric Tree asked at Google/Amazon/Meta?

Symmetric Tree is a common entry-level tree question frequently asked in technical interviews at companies like Amazon, Meta, and Microsoft. It tests understanding of tree traversal, recursion, and mirror structure validation in binary trees.

What data structure is used in Symmetric Tree?

The problem uses a binary tree as the primary data structure. Solutions typically apply Depth-First Search with recursion or Breadth-First Search using a queue to compare mirrored nodes across the tree.

What is the time complexity of Symmetric Tree?

The optimal time complexity is O(n), where n is the number of nodes in the binary tree. Every node must be examined at least once to verify the mirror structure. Both recursive DFS and iterative BFS approaches achieve this complexity.

Comments

Now write it yourselfClose this page and solve Symmetric Tree in the editor, without looking.
Practise Symmetric Tree