Print binary tree in Spiral order

Background

Sometime back we had seen how to traverse a binary tree and print it. We saw -

• Pre-order 
• post-order
• In-order
• level order traversals

Binary Tree Traversal

In this post we will see how to print them in a spiral order.  Consider following tree -

We need to print the tree in following order - 1, 2, 3, 4, 5, 6, 7.

Code

Following recursive approach will help achieve this. Idea is to keep a boolean toggle param to print nodes either from left to right or right to left.

    public static int getHeight(BTreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = getHeight(root.getLeft());
            int rightHeight = getHeight(root.getRight());
            return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        }
    }


    /**
     * 
     * @param root
     *            if the btrr Worst case time complexity - O(N^2) for skewed
     *            trees No extra space
     */
    public static void printSpiralRecurssive(BTreeNode root) {
        boolean leftToRight = false;
        int height = getHeight(root);
        for (int i = 1; i <= height; i++) {
            printLevelRecurssive(root, i, leftToRight);
            leftToRight = !leftToRight;
        }
    }

    public static void printLevelRecurssive(BTreeNode root, int level, boolean leftToRight) {
        if (level == 1) {
            System.out.println(root.getData());
        } else {
            if (leftToRight) {
                printLevelRecurssive(root.getLeft(), level - 1, leftToRight);
                printLevelRecurssive(root.getRight(), level - 1, leftToRight);
            } else {
                printLevelRecurssive(root.getRight(), level - 1, leftToRight);
                printLevelRecurssive(root.getLeft(), level - 1, leftToRight);
            }
        }
    }

Logic : We first calculate the height of the tree which are basically levels. We then iterate from 1 to height (basically all levels) and print them from left to right or right to left based on the boolean toggle. We toggle this value after each level. For each recursive call we start from root and we go down till we reach the level we want it to be (one next to previously iterated on) based on the height and print nodes.

Complete solution with example is provide under my github repo of Data Structures -

• https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/utils/BTreePrinter.java

In the same link there is a recursive solution as well that takes O(N) extra space to give same result. Iterative solution  -

private static Stack<BTreeNode> leftToRight = new Stack<>();
private static Stack<BTreeNode> rightToLeft = new Stack<>();
public static void printSpiralIterative(BTreeNode root) {

        rightToLeft.push(root);

        while (!rightToLeft.isEmpty() && !leftToRight.isEmpty()) {
            while (!rightToLeft.isEmpty()) {
                BTreeNode node = rightToLeft.pop();
                System.out.println(node.getData());
                if (node.getLeft() != null) {
                    leftToRight.push(node.getLeft());
                }
                if (node.getRight() != null) {
                    leftToRight.push(node.getRight());
                }
            }

            while (!leftToRight.isEmpty()) {
                BTreeNode node = rightToLeft.pop();
                System.out.println(node.getData());
                if (node.getLeft() != null) {
                    rightToLeft.push(node.getLeft());
                }
                if (node.getRight() != null) {
                    rightToLeft.push(node.getRight());
                }
            }
        }

}

Let me know if you have any questions.

Related Links

• Binary Tree Traversal(OSFG)
• Level order traversal in spiral form(GFG)
• https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/utils/BTreePrinter.java