Coding Interview PatternsSymmetric Tree
EasyTree Depth-First Search

Symmetric Tree

Explanation & Solution

Practice Problem

Description

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

Examples

Example 1:

```tree

[1, 2, 2, 3, 4, 4, 3]

`

Input:root = [1, 2, 2, 3, 4, 4, 3]
0
1
1
2
2
2
3
3
4
4
5
4
6
3

Output: true

Explanation: The tree is symmetric. The left subtree [2, 3, 4] is a mirror of the right subtree [2, 4, 3].

Example 2:

```tree

[1, 2, 2, null, 3, null, 3]

`

Input:root = [1, 2, 2, null, 3, null, 3]
0
1
1
2
2
2
3
null
4
3
5
null
6
3

Output: false

Explanation: The tree is not symmetric. Both sides have a 3 on the right, but a mirror would require a 3 on the left of the right subtree.

Example 3:

```tree

[1]

`

Input:root = [1]
0
1

Output: true

Constraints

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

Approach

Tree Depth-First Search pattern

1. Base Case

  • If root is null:
  • Return true
  • An empty tree is symmetric

2. Initialize BFS with Pairs

  • Create a queue with two elements: [root.left, root.right]
  • We compare mirror-position nodes in pairs

3. Process Pairs

  • While the queue is not empty:
  • Dequeue two nodes: left and right
  • Both null: Continue (symmetric at this position)
  • One null, one not: Return false (asymmetric structure)
  • Values differ: Return false (asymmetric values)
  • Values match: Enqueue their children in mirror order:
  • left.left with right.right (outer pair)
  • left.right with right.left (inner pair)

4. Mirror Order is Key

  • For a symmetric tree:
  • The left child of the left subtree must equal the right child of the right subtree
  • The right child of the left subtree must equal the left child of the right subtree
  • This is why we push (left.left, right.right) and (left.right, right.left)

5. Return True

  • If we process all pairs without finding asymmetry, the tree is symmetric

Key Insight

  • Instead of comparing levels, we compare mirror-position pairs using BFS
  • Each pair consists of two nodes that should be equal in a symmetric tree
Time
O(n)visit each node once
Space
O(n)for the queue

Visualization

Input:
DFS Traversal[1, 2, 2, 3, 4, 4, 3]
1223443
output0

Press play to start DFS traversal

CurrentIn stackComplete
15 steps

Solution Code

Previous
Path Sum
Next
Binary Tree Maximum Path Sum