Solution: Symmetric Tree

Statement#

Given the root of a binary tree, check whether it is a symmetric tree. A symmetric tree refers to a tree that is the mirror of itself, i.e., symmetric around its root.

Constraints:

• The tree contains nodes in the range $[1, 500]$.
• $-10^3 \le$ Node.data $\le 10^3$

Solution#

Starting from the root, we have to check that the left and right subtrees of the tree are mirrors of each other. The tree containing a single element root is always symmetric; we will return TRUE in this case. Otherwise, we will use the following algorithm:

1. We take a queue with root's right and left nodes.
2. Iterate a loop till the queue is not empty.
3. In each iteration, we dequeue two elements from the queue and store them in two variables, left and right.
   • If both left and right are NULL, it means that the node doesn’t have any child. So, we move to the next interaction.
   • If any from left and right is NULL, it means that either the left child or right child of the node doesn’t exist, which leads us to the conclusion that the tree is not symmetric; we return FALSE.
   • If the values of left and right are different, it also means that the tree is not symmetric; we return FALSE.
4. Then, we append the left node of left, the right node of right, the left node of right, and the right node of left in the queue in the same order, and we move to the next interaction.
5. After completing all interactions, if the algorithm is not returned from any step, this indicates that the tree is symmetric, so we return TRUE.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s have a look at the code for the algorithm we just discussed.

Note: This can also be achieved using a stack instead of a queue.

Time complexity#

The time complexity of this solution is $O(n)$, where $n$ is the total number of nodes in the tree. This is because we traverse the entire tree once.

Space complexity#

Additional space is required to store a maximum of $n$ elements in the queue, where $n$ is the total number of nodes in the tree. So, the space complexity of this solution is $O(n)$.