Symmetric Tree

Symmetric Tree

What is this problem about?

The Symmetric Tree interview question asks you to determine if a binary tree is a mirror of itself. In other words, if you were to draw a line vertically through the root, the left and right subtrees should be identical in structure and values but flipped. For a tree to be symmetric, the left child of the left subtree must be identical to the right child of the right subtree, and the right child of the left subtree must be identical to the left child of the right subtree.

Why is this asked in interviews?

This is a classic "Easy" problem asked by companies like Apple, Meta, and Amazon. It is an excellent test of a candidate's recursive thinking. It evaluates whether you can define the "symmetry" condition correctly and implement a traversal that compares two different subtrees simultaneously. It also offers a chance to demonstrate knowledge of iterative tree traversal using a queue (BFS).

Algorithmic pattern used

The primary algorithmic patterns are Depth-First Search (DFS) and Breadth-First Search (BFS).

• Recursive (DFS): Create a helper function isMirror(node1, node2). The base cases are if both are null (true) or one is null (false). The recursive step checks if node1.val == node2.val and calls isMirror(node1.left, node2.right) and isMirror(node1.right, node2.left).
• Iterative (BFS): Use a queue and push nodes in pairs (left child of one, right child of the other, and vice versa). At each step, pull two nodes and compare them.

Example explanation

Tree: 1 /
2 2 / \ /
3 4 4 3

• Root is 1. Compare left subtree (root 2) and right subtree (root 2).
• Compare left-left (3) and right-right (3). Match!
• Compare left-right (4) and right-left (4). Match! Tree is symmetric. If the right-right child was 5 instead of 3, the tree would not be symmetric.

Common mistakes candidates make

A common mistake is trying to use an in-order traversal and checking if the resulting array is a palindrome. This doesn't work because in-order traversal doesn't uniquely represent the tree structure (different trees can have the same in-order traversal). Another mistake is failing to handle null checks properly, which can lead to NullPointerException errors during the comparison.

Interview preparation tip

For the Symmetric Tree coding problem, focus on mastering the Tree traversal interview pattern. Practice comparing two trees (the "Same Tree" problem) as it is the foundation for this question. Also, understand how to convert your recursive solution into an iterative one using a queue or stack, as interviewers often ask for both.