The zigzag traversal of a binary tree means for the node at the top level we go from left to right, then for the next level, we go from right to left, and thus, we keep on changing the direction from left to right, and then from right to left. Note that at the top level, we can go from right to left, instead of left to right, then for the next level, we have to go from left to right. The important point to remember for the zigzag traversal of a binary tree in Java is that at each level, the direction of traversal is opposite of the previous level. In this tutorial, we will discuss the various approaches using which one can achieve the zigzag traversal of a binary tree. Note that each approach is very important from the interview point of view.
The zigzag traversal is: 18 30 20 60 34 45 65 41 71 59 31 82 98 50 12
