Given a binary tree, check whether it is a mirror of itself without recursion.
Input : 1 / 2 2 / / 3 4 4 3 Output : Symmetric Input : 1 / 2 2 3 3 Output : Not Symmetric
We have discussed recursive approach to solve this problem in below post :
In this post, iterative approach is discussed. We use Queue here. Note that for a symmetric that elements at every level are palindromic. In example 2, at the leaf level- the elements are which is not palindromic.
In other words,
1. The left child of left subtree = right child of right subtree.
2. The right child of left subtree = left child of right subtree.
If we insert the left child of left subtree first followed by right child of the right subtree in the queue, we only need to ensure that these are equal.
Similarly, If we insert the right child of left subtree followed by left child of the right subtree in the queue, we again need to ensure that these are equal.
Below is the implementation based on above idea.
The given tree is Symmetric
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.