Printing elements of a Binary Tree in Spiral Order Traversal using Java.

Hello Friends,

I am here again with yet another algorithm. Lets say we have a binary tree and we wish to traverse it in a special way.
Lets start traversal of the tree from left starting at the 0th level i.e. the root element. As we move to the next level i.e. level 1 then lets start the traversal from right so all the children of the root are traversed right to left. As we move to next level lets reverse the direction of traversal.






For example for the graph above the traversal should be like 1 2 3 4 6 5 7 8. At each level the traversal direction is changed and we start from root with left direction.

Friends, please have a look at the code below for the implementation of this type of traversal. I have used ArrayDeque to get the implementation of Stack ( java.util.Stack has all its methods synchronized and I do not need synchronization in my current implementation, hence I have used java.util.ArrayDeque). We can eaisly replace the ArrayDeque with our custom stack if we want, but for this example below lets proceed with ArrayDeque.

import java.util.ArrayDeque;

public class SpiralBinaryTreeTraversal {

    public static void main(String[] args) {
        int[] nodes = { 1, 2, 3, 4, 5, 6, 7, 8 };
        int left[] = { -1, 3, -1, -1, 7, -1, -1, -1 };
        int right[] = { 2, 4, 5, 6, 8, - 1, -1, -1 };
        printSpiral(nodes, left, right);
    }

    public static void printSpiral(int nodes[], int left[], int right[]) {
        ArrayDeque<Integer> leftStack = new ArrayDeque<>();
        ArrayDeque<Integer> rightStack = new ArrayDeque<>();
        leftStack.push(nodes[0]);
        boolean isLeft = true;
        int current, currentIndex;
        while(!leftStack.isEmpty() || !rightStack.isEmpty()){
            if(isLeft){
                current = leftStack.pop();
                currentIndex = current-1;
                if(left[currentIndex] != -1){
                    rightStack.push(left[currentIndex]);
                }
                if(right[currentIndex] != -1){
                    rightStack.push(right[currentIndex]);
                }
                System.out.println(current);
                if(leftStack.isEmpty()){
                    isLeft = !isLeft;
                }
            }else{
                current = rightStack.pop();
                currentIndex = current-1;
                if(right[currentIndex] != -1){
                    leftStack.push(right[currentIndex]);
                }
                if(left[currentIndex] != -1){
                    leftStack.push(left[currentIndex]);
                }
                System.out.println(current);
                if(rightStack.isEmpty()){
                    isLeft = !isLeft;
                }
            }
        }
    }
}