Symmetric Tree - Video Solutions

Problem Overview: Given the root of a binary tree, determine whether the tree is symmetric around its center. A tree is symmetric if the left subtree is a mirror reflection of the right subtree.

Approach 1: Recursive Mirror Check (Depth-First Search) (Time: O(n), Space: O(h))

This approach compares the left and right subtrees using recursion. Two nodes are considered mirrors if their values are equal and their children are symmetric in opposite order: left.left matches right.right and left.right matches right.left. Start by calling a helper function with the root’s left and right children. The recursion continues until both nodes are null (symmetric) or a mismatch appears. Because every node is visited once, the time complexity is O(n). The recursion stack uses O(h) space where h is the tree height. This method is the most intuitive way to reason about symmetry in a binary tree and naturally fits depth-first search patterns.

Approach 2: Iterative Queue Comparison (Breadth-First Search) (Time: O(n), Space: O(n))

The iterative approach replaces recursion with a queue. Push the root’s left and right children as a pair. At each step, pop two nodes and compare them. If both are null, continue. If only one is null or their values differ, the tree is not symmetric. Otherwise, push their children in mirrored order: left.left with right.right, and left.right with right.left. The queue ensures nodes are processed level by level while maintaining mirror pairing. Each node enters the queue at most once, giving O(n) time and O(n) space in the worst case. This version mirrors the recursive logic but uses explicit state management, a common technique in breadth-first search problems.

Recommended for interviews: The recursive DFS solution is typically expected because the mirror relationship is easy to express with a helper function. It clearly demonstrates your understanding of recursion and tree structure. The iterative queue approach shows deeper control over traversal mechanics and avoids recursion stack limits. Mentioning both approaches during interviews signals strong mastery of tree traversal patterns.