Symmetric Tree

Given a binary tree, return whether or not it forms a reflection across its center (i.e. a line drawn straight down starting from the root).

Note: A reflection is when an image, flipped across a specified line, forms the same image.

Example(s)

Example 1:

Input:
   2
 /   \
1     1

Output: true
Explanation:
When reflected across the center, the tree forms the same image.
Left subtree (1) is a mirror of right subtree (1).

Example 2:

Input:
    1
   / \
  5   5
   \    \
    7    7

Output: false
Explanation:
When reflected across the center, the nodes containing 7s do not match.
Left subtree: 5 -> 7 (right child)
Right subtree: 5 -> 7 (right child)
But for symmetry, left's right should mirror right's left.
Here, both have right children, so they don't mirror.

Example 3:

Input:
    1
   / \
  2   2
 / \ / \
3  4 4  3

Output: true
Explanation:
The tree is symmetric:
  Left subtree:     Right subtree:
      2                 2
     / \               / \
    3   4             4   3
Left's left (3) mirrors right's right (3)
Left's right (4) mirrors right's left (4)

Example 4:

Input:
    1
   / \
  2   2
   \   \
    3    3

Output: true
Explanation:
Left subtree: 2 -> 3 (right)
Right subtree: 2 -> 3 (left)
They mirror each other.

Solution

The solution uses DFS (Depth-First Search):

Two-node comparison: Compare left and right subtrees as mirror images
Recursive check: For two nodes to be mirrors:
- Their values must be equal
- Left's left must mirror right's right
- Left's right must mirror right's left
Base cases: Both null (symmetric), one null (not symmetric)

JavaScript Solution
Python Solution

JavaScript Solution - DFS

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

/**
* Check if binary tree is symmetric
* @param {TreeNode} root - Root of binary tree
* @return {boolean} - Whether tree is symmetric
*/
function isSymmetric(root) {
if (!root) return true;

/**
 * Check if two subtrees are mirror images
 * @param {TreeNode} left - Left subtree root
 * @param {TreeNode} right - Right subtree root
 * @return {boolean} - Whether they are mirrors
 */
function isMirror(left, right) {
  // Base case: both are null
  if (!left && !right) return true;
  
  // Base case: one is null, other is not
  if (!left || !right) return false;
  
  // Values must be equal
  if (left.val !== right.val) return false;
  
  // Recursively check:
  // Left's left must mirror right's right
  // Left's right must mirror right's left
  return isMirror(left.left, right.right) && 
         isMirror(left.right, right.left);
}

return isMirror(root.left, root.right);
}

// Helper function to create tree nodes for testing
function TreeNode(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}

// Test cases
// Example 1: [2, 1, 1]
const tree1 = new TreeNode(2,
new TreeNode(1),
new TreeNode(1)
);
console.log('Example 1:', isSymmetric(tree1)); // true

// Example 2: [1, 5, 5, null, 7, null, 7]
const tree2 = new TreeNode(1,
new TreeNode(5, null, new TreeNode(7)),
new TreeNode(5, null, new TreeNode(7))
);
console.log('Example 2:', isSymmetric(tree2)); // false

// Example 3: [1, 2, 2, 3, 4, 4, 3]
const tree3 = new TreeNode(1,
new TreeNode(2, new TreeNode(3), new TreeNode(4)),
new TreeNode(2, new TreeNode(4), new TreeNode(3))
);
console.log('Example 3:', isSymmetric(tree3)); // true

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - DFS

# 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

from typing import Optional

def is_symmetric(root: Optional[TreeNode]) -> bool:
  """
  Check if binary tree is symmetric
  
  Args:
      root: Root of binary tree
      
  Returns:
      bool: Whether tree is symmetric
  """
  if not root:
      return True
  
  def is_mirror(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
      """
      Check if two subtrees are mirror images
      
      Args:
          left: Left subtree root
          right: Right subtree root
          
      Returns:
          bool: Whether they are mirrors
      """
      # Base case: both are null
      if not left and not right:
          return True
      
      # Base case: one is null, other is not
      if not left or not right:
          return False
      
      # Values must be equal
      if left.val != right.val:
          return False
      
      # Recursively check:
      # Left's left must mirror right's right
      # Left's right must mirror right's left
      return is_mirror(left.left, right.right) and              is_mirror(left.right, right.left)
  
  return is_mirror(root.left, root.right)

# Helper class for testing
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

# Test cases
# Example 1: [2, 1, 1]
tree1 = TreeNode(2,
  TreeNode(1),
  TreeNode(1)
)
print('Example 1:', is_symmetric(tree1))  # True

# Example 2: [1, 5, 5, None, 7, None, 7]
tree2 = TreeNode(1,
  TreeNode(5, None, TreeNode(7)),
  TreeNode(5, None, TreeNode(7))
)
print('Example 2:', is_symmetric(tree2))  # False

# Example 3: [1, 2, 2, 3, 4, 4, 3]
tree3 = TreeNode(1,
  TreeNode(2, TreeNode(3), TreeNode(4)),
  TreeNode(2, TreeNode(4), TreeNode(3))
)
print('Example 3:', is_symmetric(tree3))  # True

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Iterative with Queue)

Here's an iterative solution using a queue:

JavaScript Iterative
Python Iterative

/**
 * Iterative solution using queue
 */
function isSymmetricIterative(root) {
  if (!root) return true;
  
  const queue = [root.left, root.right];
  
  while (queue.length > 0) {
    const left = queue.shift();
    const right = queue.shift();
    
    // Both null, continue
    if (!left && !right) continue;
    
    // One null, not symmetric
    if (!left || !right) return false;
    
    // Values don't match, not symmetric
    if (left.val !== right.val) return false;
    
    // Add children in mirror order
    queue.push(left.left, right.right);
    queue.push(left.right, right.left);
  }
  
  return true;
}

from collections import deque

def is_symmetric_iterative(root: Optional[TreeNode]) -> bool:
    """
    Iterative solution using queue
    """
    if not root:
        return True
    
    queue = deque([root.left, root.right])
    
    while queue:
        left = queue.popleft()
        right = queue.popleft()
        
        # Both null, continue
        if not left and not right:
            continue
        
        # One null, not symmetric
        if not left or not right:
            return False
        
        # Values don't match, not symmetric
        if left.val != right.val:
            return False
        
        # Add children in mirror order
        queue.append(left.left)
        queue.append(right.right)
        queue.append(left.right)
        queue.append(right.left)
    
    return True

Complexity

Time Complexity: O(n) - Where n is the number of nodes in the tree. We visit each node once.
Space Complexity:
- Recursive: O(h) - Where h is the height of the tree. For the recursion stack. In worst case (skewed tree), O(n). In average case (balanced tree), O(log n).
- Iterative: O(n) - For the queue in worst case.

Approach

The solution uses DFS (Depth-First Search):

Two-node comparison:
- Compare left and right subtrees as mirror images
- Use a helper function isMirror(left, right)
Mirror check conditions:
- Both nodes are null → symmetric (base case)
- One is null, other is not → not symmetric
- Values don't match → not symmetric
- Recursively check:
  - left.left mirrors right.right
  - left.right mirrors right.left
Recursive structure:
- For two nodes to be mirrors, their subtrees must also be mirrors
- This creates the recursive structure

Key Insights

Mirror property: Left subtree must be mirror of right subtree
Cross comparison: Left's left mirrors right's right, left's right mirrors right's left
Base cases: Both null (symmetric), one null (not symmetric)
O(n) time: Must visit all nodes
O(h) space: Recursion stack depth

Step-by-Step Example

Let's trace through Example 1:

Tree:
   2
 /   \
1     1

isSymmetric(root=2):
  Check: isMirror(1, 1)
    left=1, right=1
    Both not null ✓
    left.val (1) === right.val (1) ✓
    Check: isMirror(1.left, 1.right)
      left.left=null, right.right=null
      Both null → return true ✓
    Check: isMirror(1.right, 1.left)
      left.right=null, right.left=null
      Both null → return true ✓
    Return: true && true = true ✓

Result: true

Let's trace through Example 2:

Tree:
    1
   / \
  5   5
   \    \
    7    7

isSymmetric(root=1):
  Check: isMirror(5, 5)
    left=5, right=5
    Both not null ✓
    left.val (5) === right.val (5) ✓
    Check: isMirror(5.left, 5.right)
      left.left=null, right.right=null
      Both null → return true ✓
    Check: isMirror(5.right, 5.left)
      left.right=7, right.left=null
      One null, other not → return false ✗
    Return: true && false = false ✗

Result: false

Visual Representation

Example 1: Symmetric
   2
 /   \
1     1

Mirror check:
  Left subtree (1) vs Right subtree (1)
    Values: 1 === 1 ✓
    Left's left (null) vs Right's right (null) ✓
    Left's right (null) vs Right's left (null) ✓
  Result: true ✓

Example 2: Not symmetric
    1
   / \
  5   5
   \    \
    7    7

Mirror check:
  Left subtree (5) vs Right subtree (5)
    Values: 5 === 5 ✓
    Left's left (null) vs Right's right (null) ✓
    Left's right (7) vs Right's left (null) ✗
      One is null, other is not
  Result: false ✗

Example 3: Symmetric
    1
   / \
  2   2
 / \ / \
3  4 4  3

Mirror check:
  Left subtree (2) vs Right subtree (2)
    Values: 2 === 2 ✓
    Left's left (3) vs Right's right (3) ✓
    Left's right (4) vs Right's left (4) ✓
  Result: true ✓

Edge Cases

Empty tree: Return true (empty tree is symmetric)
Single node: Return true (single node is symmetric)
Only left child: Return false (not symmetric)
Only right child: Return false (not symmetric)
All same values but different structure: Check structure, not just values

Important Notes

Mirror property: Left subtree must mirror right subtree
Cross comparison: Compare left's left with right's right, etc.
Structure matters: Same values but different structure → not symmetric
O(n) time: Must visit all nodes
O(h) space: Recursion stack depth

Why DFS Works

Key insight:

A tree is symmetric if its left and right subtrees are mirror images
Two subtrees are mirrors if:
- Their roots have the same value
- Left's left subtree mirrors right's right subtree
- Left's right subtree mirrors right's left subtree
This creates a recursive structure that DFS can handle

Optimal substructure:

If we know two subtrees are mirrors, we can check if their parent trees are mirrors
The recursive structure naturally fits DFS

Same Tree: Check if two trees are identical
Invert Binary Tree: Mirror the entire tree
Maximum Depth of Binary Tree: Different tree problem
Balanced Binary Tree: Different tree property

Takeaways

DFS traversal compares left and right subtrees
Mirror check requires cross comparison (left's left vs right's right)
O(n) time to visit all nodes
O(h) space for recursion stack
Classic tree problem with recursive structure

Example(s)​

Solution​

JavaScript Solution - DFS

Output:

Python Solution - DFS

Output:

Alternative Solution (Iterative with Queue)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Why DFS Works​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Iterative with Queue)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Why DFS Works

Related Problems

Takeaways