Symmetric Tree

Check if a binary tree is symmetric around its center.

Language Selection

Choose your preferred programming language

Showing: Python

Symmetric Tree

Problem Statement

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

Examples

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true
Explanation: The tree is symmetric around its center.

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false
Explanation: The tree is not symmetric.

Example 3:

Input: root = [1]
Output: true
Explanation: Single node tree is symmetric.

Constraints

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

Approach 1: Recursive DFS (Optimal)

Algorithm

Use recursion to check if left and right subtrees are mirrors of each other.

Steps:

Check if root is null (symmetric)
Recursively check if left and right subtrees are mirrors
Two nodes are mirrors if:
- Their values are equal
- Left subtree of first node mirrors right subtree of second node
- Right subtree of first node mirrors left subtree of second node

Implementation

Python:

def isSymmetric(root):
    """
    Check if binary tree is symmetric using recursive DFS
    Time: O(n)
    Space: O(h) where h is height of tree
    """
    if not root:
        return True
    
    def isMirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        
        return (isMirror(left.left, right.right) and 
                isMirror(left.right, right.left))
    
    return isMirror(root.left, root.right)

Java:

class Solution {
    /**
     * Check if binary tree is symmetric using recursive DFS
     * Time: O(n)
     * Space: O(h) where h is height of tree
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        return isMirror(root.left, root.right);
    }
    
    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        
        return isMirror(left.left, right.right) && 
               isMirror(left.right, right.left);
    }
}

Go:

func isSymmetric(root *TreeNode) bool {
    /**
     * Check if binary tree is symmetric using recursive DFS
     * Time: O(n)
     * Space: O(h) where h is height of tree
     */
    if root == nil {
        return true
    }
    
    return isMirror(root.Left, root.Right)
}

func isMirror(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)
}

JavaScript:

/**
 * Check if binary tree is symmetric using recursive DFS
 * Time: O(n)
 * Space: O(h) where h is height of tree
 */
function isSymmetric(root) {
    if (!root) {
        return true;
    }
    
    function isMirror(left, right) {
        if (!left && !right) {
            return true;
        }
        if (!left || !right) {
            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);
}

C#:

public class Solution {
    /// <summary>
    /// Check if binary tree is symmetric using recursive DFS
    /// Time: O(n)
    /// Space: O(h) where h is height of tree
    /// </summary>
    public bool IsSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        return IsMirror(root.left, root.right);
    }
    
    private bool IsMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        
        return IsMirror(left.left, right.right) && 
               IsMirror(left.right, right.left);
    }
}

Complexity Analysis

Time Complexity: O(n) - Visit each node exactly once
Space Complexity: O(h) - Recursion stack depth equals tree height

Key Insights

Mirror Property: Left and right subtrees must be mirrors
Recursive Approach: Most intuitive and elegant solution
Iterative Alternative: Use queue for BFS approach
Null Handling: Both nodes must be null or both must be non-null
Value Comparison: Node values must be equal for symmetry

Edge Cases

Empty Tree: Should return true (symmetric)
Single Node: Should return true (symmetric)
Skewed Tree: Handle left-skewed or right-skewed trees
Perfect Tree: Handle balanced trees efficiently
Asymmetric Tree: Handle trees with different structures

Test Cases

def test_isSymmetric():
    # Test case 1: Symmetric tree
    root1 = TreeNode(1)
    root1.left = TreeNode(2)
    root1.right = TreeNode(2)
    root1.left.left = TreeNode(3)
    root1.left.right = TreeNode(4)
    root1.right.left = TreeNode(4)
    root1.right.right = TreeNode(3)
    
    assert isSymmetric(root1) == True
    
    # Test case 2: Asymmetric tree
    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.right = TreeNode(2)
    root2.left.right = TreeNode(3)
    root2.right.right = TreeNode(3)
    
    assert isSymmetric(root2) == False
    
    # Test case 3: Single node
    root3 = TreeNode(1)
    assert isSymmetric(root3) == True
    
    # Test case 4: Empty tree
    assert isSymmetric(None) == True
    
    print("All tests passed!")

test_isSymmetric()

Follow-up Questions

Symmetric Tree II: Check symmetry for n-ary tree?
Symmetric Tree with Values: Check symmetry ignoring values?
Symmetric Tree with Structure: Check symmetry ignoring structure?
Symmetric Tree with Paths: Check if all paths are symmetric?
Symmetric Tree with Levels: Check symmetry level by level?

Common Mistakes

Not Handling Nulls: Forgetting to check for null nodes
Wrong Mirror Logic: Incorrectly comparing left-left with right-left
Missing Base Cases: Not handling empty tree or single node
Value Comparison: Not comparing node values for equality
Recursion Depth: Not considering stack overflow for deep trees

Interview Tips

Start with Recursion: Most intuitive approach
Explain Mirror Logic: Show understanding of symmetry concept
Handle Edge Cases: Mention empty tree and single node cases
Discuss Trade-offs: Compare recursive vs iterative approaches
Follow-up Ready: Be prepared for variations and optimizations

Concept Explanations

Symmetric Tree: A binary tree is symmetric if it is a mirror image of itself around its center. This means the left subtree is a mirror of the right subtree.

Mirror Property: Two nodes are mirrors if:

Their values are equal
The left subtree of the first node mirrors the right subtree of the second node
The right subtree of the first node mirrors the left subtree of the second node

Recursive Approach: We recursively check if the left and right subtrees are mirrors by comparing their values and recursively checking their children in mirror order.

Why Recursion Works: The problem has a recursive structure - if we can determine that two subtrees are mirrors, we can determine if the entire tree is symmetric.

Null Handling: We need to handle null nodes carefully. Two null nodes are considered mirrors, but a null node and a non-null node are not mirrors.