Skip to main content
Talentd

Symmetric Tree - Solution & Explanation

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree22 min readAsked at: Amazon, Microsoft, Apple +8
Practice this problem

Problem Statement

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.

This C code defines a recursive function isMirror that checks if two trees are mirror images. The isSymmetric function calls isMirror with the root node passed twice. The function checks if both nodes are null (returns true if so) or if one is null (returns false). It then checks if the values are the same and recursively calls isMirror on the opposite children nodes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree, since we traverse every node once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion call stack.

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.

This C solution employs a queue data structure for comparing values of nodes iteratively. A newly defined data structure and its pertinent functions encapsulate the queue. The code mimics the recursive solution’s pattern: null-checking nodes, confirming equality of values, and inserting children appropriately for subsequent comparisons.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), n being indicative of the number of nodes enumerated.
Space Complexity: O(n), underscored by the queue's need for storing nodes in tandem with iteration.

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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach

Time Complexity: O(n), where n is the number of nodes in the binary tree, since we traverse every node once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion call stack.

Iterative Approach

Time Complexity: O(n), n being indicative of the number of nodes enumerated.
Space Complexity: O(n), underscored by the queue's need for storing nodes in tandem with iteration.

Recursion—

Detailed 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

Video Solution

Symmetric Tree - Leetcode 101 - Python • NeetCodeIO • 66,727 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Symmetric Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II