Symmetric Tree | Leetcode 101

Welcome to our deep dive on Symmetric Tree (Leetcode 101). This problem extends standard DFS patterns by requiring simultaneous traversal of two separate tree branches.

Problem Statement

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

Example 1: root = [1,2,2,3,4,4,3] => Output: true

Example 2: root = [1,2,2,null,3,null,3] => Output: false

Approach: Recursive Mirrored DFS O(N)

To determine if a tree is symmetric, its root's left subtree and right subtree must be perfectly mirrored reflections of each other.

To prove two subtrees left_node and right_node are mirrored, they must fulfill three combined conditions:

1. Their root values must be identical.
2. The left_node.left subtree must mirror the right_node.right subtree.
3. The left_node.right subtree must mirror the right_node.left subtree.

We can solve this intuitively using DFS by passing down two separate node pointers concurrently.

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
            
        def isMirror(left_node, right_node):
            if not left_node and not right_node:
                return True
            if not left_node or not right_node:
                return False
                
            return (left_node.val == right_node.val) and \
                   isMirror(left_node.left, right_node.right) and \
                   isMirror(left_node.right, right_node.left)
                   
        return isMirror(root.left, root.right)

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (101)