LeetCode 101 - Symmetric Tree

LeetCode Problem 101

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to determine whether a binary tree is symmetric around its center. A tree is symmetric if the left subtree is a mirror reflection of the right subtree.

In a mirror relationship, the following conditions must hold:

• The values of the corresponding nodes must be equal.
• The left child of one subtree must match the right child of the other subtree.
• The right child of one subtree must match the left child of the other subtree.

The input is the root node of a binary tree. The output is a boolean value:

• true if the tree is symmetric
• false otherwise

For example, consider this tree:

        1
      /   \
     2     2
    / \   / \
   3   4 4   3

This tree is symmetric because the left and right sides are exact mirror images.

Now consider:

        1
      /   \
     2     2
      \     \
       3     3

This tree is not symmetric because the structure itself differs. The left subtree has a missing left child, while the right subtree has a missing left child in a different mirrored position.

The constraints tell us that the tree contains at most 1000 nodes. This is small enough for both recursive and iterative traversals. Since the problem explicitly mentions recursive and iterative solutions, we should understand both approaches.

Several edge cases are important:

• A tree with only one node is symmetric.
• Trees with missing children can easily break symmetry.
• Equal values alone are not sufficient, the structure must also mirror correctly.
• Null nodes must be handled carefully, because mirrored positions may both be empty, which is valid.

Approaches

Brute Force Approach

A brute force solution would explicitly construct two traversal representations and compare them.

One possible strategy is:

1. Traverse the left subtree in a normal order.
2. Traverse the right subtree in mirrored order.
3. Include null markers so structural differences are preserved.
4. Compare the resulting sequences.

For example, we could perform:

• preorder traversal on the left subtree
• mirrored preorder traversal on the right subtree

If the sequences match exactly, the tree is symmetric.

This approach works because it serializes both sides in a way that preserves both node values and structure. Without null markers, structurally different trees could incorrectly appear equal.

However, this method uses extra memory to store traversal results and performs unnecessary serialization work. We do not actually need complete traversal arrays. We only need to compare corresponding nodes directly.

Optimal Approach

The key insight is that symmetry is fundamentally a pairwise comparison problem.

Instead of serializing the tree, we can directly compare two nodes at a time:

• The values must match.
• One node's left child must match the other node's right child.
• One node's right child must match the other node's left child.

This naturally leads to a recursive depth first search solution.

We define a helper function:

isMirror(node1, node2)

This function checks whether two subtrees are mirror images.

The recursive relationship is:

isMirror(a, b) =
    a.val == b.val
    AND isMirror(a.left, b.right)
    AND isMirror(a.right, b.left)

This avoids unnecessary storage and processes the tree directly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Serializes both subtrees into arrays
Optimal	O(n)	O(h)	Direct recursive mirror comparison

Here:

• n is the number of nodes
• h is the height of the tree

Algorithm Walkthrough

Recursive Mirror Comparison

1. Start from the root node and compare its left and right subtrees.

The root itself does not need comparison against another node. Symmetry depends entirely on whether its two subtrees mirror each other. 2. Create a helper function that accepts two nodes.

This helper determines whether the two subtrees are mirror images. 3. If both nodes are None, return True.

Two empty subtrees are symmetric by definition. 4. If exactly one node is None, return False.

One subtree exists while the other does not, so the structure is not mirrored. 5. Compare the node values.

If the values differ, symmetry is broken immediately. 6. Recursively compare the outer children.

Compare:

• left subtree of the first node
• right subtree of the second node

7. Recursively compare the inner children.

Compare:

• right subtree of the first node
• left subtree of the second node

8. Return True only if both recursive comparisons succeed.

Both structural and value symmetry must hold throughout the entire tree.

Why it works

The algorithm maintains the invariant that every recursive call compares nodes that should occupy mirrored positions in a symmetric tree.

At each step:

• corresponding values must match
• corresponding mirrored children must also match

If this property holds for all recursive calls, then the entire tree is symmetric. If any mismatch occurs, the tree cannot be a mirror of itself.

Python Solution

# 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

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        
        def is_mirror(left: Optional[TreeNode],
                      right: Optional[TreeNode]) -> bool:
            
            if left is None and right is None:
                return True
            
            if left is None or right is None:
                return False
            
            if left.val != right.val:
                return False
            
            return (
                is_mirror(left.left, right.right)
                and
                is_mirror(left.right, right.left)
            )
        
        return is_mirror(root.left, root.right)

The implementation follows the recursive mirror comparison directly.

The helper function is_mirror receives two nodes that should mirror each other.

The first condition handles the case where both nodes are absent. This represents perfectly mirrored empty subtrees.

The second condition handles structural mismatches. If one node exists and the other does not, symmetry fails immediately.

The third condition compares node values. Even if the structure is mirrored, differing values invalidate symmetry.

Finally, the recursive calls compare:

• outer children
• inner children

The use of logical and ensures that every mirrored pair must match for the tree to remain symmetric.

The main function simply starts the comparison using the root's left and right children.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {

    var isMirror func(left, right *TreeNode) bool

    isMirror = func(left, right *TreeNode) bool {

        if left == nil && right == nil {
            return true
        }

        if left == nil || right == nil {
            return false
        }

        if left.Val != right.Val {
            return false
        }

        return isMirror(left.Left, right.Right) &&
            isMirror(left.Right, right.Left)
    }

    return isMirror(root.Left, root.Right)
}

The Go implementation mirrors the Python solution closely.

The main difference is explicit pointer handling with nil instead of None.

Go uses a function variable declaration for recursion:

var isMirror func(left, right *TreeNode) bool

This allows the anonymous function to recursively reference itself.

The recursive logic remains identical:

• both nil means symmetric
• one nil means asymmetric
• unequal values fail
• mirrored child comparisons continue recursively

No integer overflow concerns exist because node values are small and we only perform equality comparisons.

Worked Examples

Example 1

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

We begin with:

is_mirror(2, 2)

Step	Left Node	Right Node	Result
1	2	2	values match
2	3	3	outer children match
3	None	None	symmetric
4	None	None	symmetric
5	4	4	inner children match
6	None	None	symmetric
7	None	None	symmetric

Every recursive comparison succeeds.

Final result:

True

Example 2

Input:
        1
      /   \
     2     2
      \     \
       3     3

We begin with:

is_mirror(2, 2)

Step	Left Node	Right Node	Result
1	2	2	values match
2	None	3	mismatch
3	recursion stops	recursion stops	asymmetric

The structure is not mirrored.

Final result:

False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited once
Space	O(h)	Recursive call stack height

The algorithm processes each node exactly one time, so the runtime is linear in the number of nodes.

The auxiliary space comes from recursion depth. In a balanced tree, the height is O(log n). In the worst case of a skewed tree, the height becomes O(n).

Test Cases

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

solution = Solution()

# Example 1
root1 = TreeNode(
    1,
    TreeNode(2, TreeNode(3), TreeNode(4)),
    TreeNode(2, TreeNode(4), TreeNode(3))
)
assert solution.isSymmetric(root1) == True  # perfectly symmetric tree

# Example 2
root2 = TreeNode(
    1,
    TreeNode(2, None, TreeNode(3)),
    TreeNode(2, None, TreeNode(3))
)
assert solution.isSymmetric(root2) == False  # structural mismatch

# Single node
root3 = TreeNode(1)
assert solution.isSymmetric(root3) == True  # single node is symmetric

# Two identical children
root4 = TreeNode(1, TreeNode(2), TreeNode(2))
assert solution.isSymmetric(root4) == True  # simple symmetric case

# Different child values
root5 = TreeNode(1, TreeNode(2), TreeNode(3))
assert solution.isSymmetric(root5) == False  # value mismatch

# Deep symmetric tree
root6 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(3),
        TreeNode(4)
    ),
    TreeNode(
        2,
        TreeNode(4),
        TreeNode(3)
    )
)
assert solution.isSymmetric(root6) == True  # deeper symmetry

# Missing mirrored node
root7 = TreeNode(
    1,
    TreeNode(2, TreeNode(3), None),
    TreeNode(2, TreeNode(3), None)
)
assert solution.isSymmetric(root7) == False  # incorrect mirrored structure

# Empty children everywhere
root8 = TreeNode(
    1,
    TreeNode(2),
    TreeNode(2)
)
assert solution.isSymmetric(root8) == True  # leaf symmetry

# Large skewed asymmetric structure
root9 = TreeNode(
    1,
    TreeNode(2, TreeNode(3)),
    TreeNode(2, TreeNode(3))
)
assert solution.isSymmetric(root9) == False  # skewed mismatch

print("All test cases passed.")

Test	Why
Perfect symmetric tree	Validates standard symmetric structure
Structural mismatch	Ensures null placement matters
Single node	Smallest valid input
Two identical children	Basic mirror validation
Different child values	Ensures value comparison works
Deep symmetric tree	Verifies recursion over multiple levels
Missing mirrored node	Detects asymmetry in structure
Leaf symmetry	Confirms simple balanced leaves
Skewed mismatch	Tests asymmetric deeper layouts

Edge Cases

Single Node Tree

A tree containing only the root node is always symmetric. There are no subtrees to compare, so the mirror condition holds trivially.

A naive implementation might incorrectly assume both left and right children must exist. Our implementation handles this correctly because the initial comparison becomes:

is_mirror(None, None)

which returns True.

Structural Asymmetry With Equal Values

One common bug is checking only node values while ignoring structure.

Consider:

    1
   / \
  2   2
   \   \
    3   3

The values appear symmetric, but the structure is not mirrored.

Our implementation explicitly checks whether one node is None while the other is not:

if left is None or right is None:
    return False

This correctly detects structural asymmetry.

Deep Recursive Comparisons

Another edge case involves deeper trees where asymmetry occurs several levels down.

For example:

        1
      /   \
     2     2
    /       \
   3         3
  /           \
 4             4

Even though upper levels appear symmetric, every recursive level must maintain the mirror relationship.

The recursive strategy naturally propagates comparisons downward and immediately stops when a mismatch occurs, ensuring correctness at all depths.