#101

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Symmetric Tree

Determine if a binary tree is symmetric by comparing left and right subtrees using DFS or BFS traversal techniques efficiently.

tree depth first search breadth first search binary tree

Problem Statement

Given the root of a binary tree, determine if the tree is a mirror of itself. The tree is symmetric if the left and right subtrees are reflections of each other at every level. You must account for null children and ensure comparisons track the exact mirrored positions.

For example, given a tree root = [1,2,2,3,4,4,3], the output should be true because the left and right subtrees reflect each other perfectly. However, for root = [1,2,2,null,3,null,3], the output is false due to asymmetry in the positions of non-null nodes.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: false

Example details omitted.

Constraints

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

Solution Approach

Recursive Depth-First Search

Perform a recursive DFS by defining a helper function that compares two nodes for symmetry. At each recursive step, compare the left child of one node with the right child of the other and vice versa. Ensure null checks are included to prevent false positives. This approach tracks state naturally via the call stack and immediately identifies asymmetry when values or structure diverge.

Iterative Breadth-First Search

Use a queue to perform level-by-level comparison. Push pairs of nodes representing mirror positions into the queue. At each step, dequeue a pair and check for value equality. If one is null and the other is not, return false. Enqueue children in mirrored order: left of first node with right of second and right of first with left of second. This BFS method tracks state explicitly and handles wide trees efficiently.

Hybrid DFS with Early Termination

Combine recursive DFS with early termination to optimize performance. When a mismatch is found between mirrored nodes, immediately return false without further recursion. This reduces unnecessary comparisons in large trees with early asymmetry. Maintain a consistent traversal order to ensure correct mirrored comparisons and leverage recursion depth as implicit state tracking.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The recursive DFS and iterative BFS approaches both traverse all nodes once, resulting in O(n) time complexity. Space complexity is O(h) for DFS due to call stack or O(n) for BFS due to the queue, where h is the tree height and n is the number of nodes. These values match the provided time and space constraints for trees with up to 1000 nodes.

What Interviewers Usually Probe

Do you account for null nodes when checking symmetry?
Can you implement both DFS and BFS approaches for mirrored comparison?
Will you detect asymmetry early to optimize traversal?

Common Pitfalls or Variants

Common pitfalls

Forgetting to compare null nodes correctly, which causes incorrect true results.
Swapping children in the wrong order during BFS, breaking the mirror logic.
Assuming symmetric values without verifying mirrored positions across the tree.

Follow-up variants

Check if an N-ary tree is symmetric using similar mirrored comparisons.
Determine symmetry for a tree with additional parent pointers included.
Validate symmetry after inserting a new node dynamically and updating subtree reflections.

FAQ

What is the main pattern in the Symmetric Tree problem?

The core pattern is binary-tree traversal with mirrored state tracking, requiring careful comparison of left and right subtrees at every node.

Can I use BFS instead of DFS to solve Symmetric Tree?

Yes, BFS works by queuing mirrored node pairs and checking their values level by level, handling nulls explicitly to maintain symmetry correctness.

How do null nodes affect symmetry checks?

Null nodes must be compared explicitly; one null and one non-null at mirrored positions immediately breaks symmetry, so they cannot be skipped.

What is a common mistake in iterative solutions?

A frequent error is enqueueing children in the wrong mirrored order, which incorrectly compares non-mirrored nodes and leads to false results.

What is the time and space complexity for this problem?

Both DFS and BFS approaches run in O(n) time for n nodes. Space is O(h) for DFS call stack or O(n) for BFS queue, where h is tree height.

terminal

Solution

Solution 1: Recursion

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> bool:
        def dfs(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
            if root1 == root2:
                return True
            if root1 is None or root2 is None or root1.val != root2.val:
                return False
            return dfs(root1.left, root2.right) and dfs(root1.right, root2.left)

        return dfs(root.left, root.right)

Continue Practicing

#100 same tree #104 maximum depth of binary tree #111 minimum depth of binary tree