Symmetric Tree

Difficulty: Easy | Acceptance: 61.10% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

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

• Examples
• Constraints
• Approach 1: Recursive Depth-First Search
• Approach 2: Iterative Depth-First Search
• Approach 3: Iterative Breadth-First Search

Examples

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

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

Constraints

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

Approach 1: Recursive Depth-First Search

Intuition A tree is symmetric if the left subtree is a mirror reflection of the right subtree. This means two trees are mirrors if their root values are equal, the left subtree of the first is a mirror of the right subtree of the second, and the right subtree of the first is a mirror of the left subtree of the second.

Steps

• Define a recursive helper function isMirror(t1, t2).
• If both t1 and t2 are null, return true.
• If only one of them is null, return false.
• If their values are different, return false.
• Recursively check if t1.left is a mirror of t2.right AND t1.right is a mirror of t2.left.
• Call the helper with root and root.

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

Complexity

• Time: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
• Space: O(h), where h is the height of the tree. This space is used by the recursion stack. In the worst case (skewed tree), this is O(n); in the best case (balanced tree), this is O(log n).
• Notes: This is the most intuitive and concise solution.

Approach 2: Iterative Depth-First Search

Intuition We can simulate the recursion using a stack. Instead of relying on the call stack to process nodes, we explicitly push pairs of nodes that need to be compared onto a stack.

Steps

• Initialize a stack and push the pair (root.left, root.right) onto it.
• While the stack is not empty:
  • Pop a pair of nodes (left, right).
  • If both are null, continue to the next iteration.
  • If only one is null or their values differ, return false.
  • Push the pairs that need to be compared next: (left.left, right.right) and (left.right, right.left).
• If the loop finishes without returning false, the tree is symmetric.

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        stack = [(root.left, root.right)]
        while stack:
            left, right = stack.pop()
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            stack.append((left.left, right.right))
            stack.append((left.right, right.left))
        return True

Complexity

• Time: O(n), as we traverse each node once.
• Space: O(h), where h is the height of the tree. The stack can grow up to the height of the tree in the worst case.
• Notes: This approach avoids recursion overhead, which can be beneficial for very deep trees to prevent stack overflow.

Approach 3: Iterative Breadth-First Search

Intuition We can use a queue to perform a level-order traversal. We compare nodes in pairs that should be mirror images of each other. This is similar to the iterative DFS approach but processes nodes level by level.

Steps

• Initialize a queue and enqueue the pair (root.left, root.right).
• While the queue is not empty:
  • Dequeue a pair of nodes (left, right).
  • If both are null, continue.
  • If only one is null or their values differ, return false.
  • Enqueue the children in the order that preserves the mirror relationship: (left.left, right.right) and (left.right, right.left).
• If the loop finishes, the tree is symmetric.

from collections import deque

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        q = deque([(root.left, root.right)])
        while q:
            left, right = q.popleft()
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            q.append((left.left, right.right))
            q.append((left.right, right.left))
        return True

Complexity

• Time: O(n), as we process every node once.
• Space: O(w), where w is the maximum width of the tree. In the worst case, this can be O(n) for a full binary tree.
• Notes: This approach is useful if you want to process the tree level by level, though it generally uses more memory than DFS for wide trees.