101. Symmetric Tree

How to solve Symmetric Tree (LeetCode 101): the approach in brief

The problem

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

Pattern

Symmetric Tree is a Tree Traversal Patterns (DFS & BFS) problem, in the Recursive Preorder Traversal subpattern. The pattern covers preorder, inorder, level order traversal, LCA, and serialization

Master preorder traversal for tree construction, inversion, and path problems. Visit root before children.

Approach outline

1. Consider which tree traversal techniques can help you compare nodes systematically on both sides of the tree.
2. Think about how you can traverse the left and right subtrees simultaneously to check for symmetry.
3. Try to define a helper function that compares two nodes and recursively checks if their subtrees are mirrors of each other.

Complexity

The reference solution runs in O(n) time and O(h) space.

Asked at

Symmetric Tree has been reported in interviews at Capital One, Amazon, Yandex, Apple, Uber, Google, Microsoft.