Monday, July 10, 2017

Level order traversal in spiral form

Printing tree in spiral form, or a zigzag form

would print 1 2 3 4 5 6 7
Algorithm

printSpiral(tree)
  set level = tree root
  while level contains nodes
     printLevel(level, ltr)
     set level = getNextLevel(level)
     ltr == !ltr 
Function to get next level
getNextLevel(level)
set nextLevel as empty list
foreach node in level
     if(node.left!=null) nextLevel.add(node.left)
     if(node.right!=null) nextLevel.add(node.right)
Function to print all nodes at a given level
printLevel(level, ltr)
if(!ltr)
    reverse level
foreach node in level
    print node.data

Example code in Java

package com.algorithms.treespiral;

import
java.util.ArrayList;
import
java.util.Collections;

public class
Main {
   
/* Driver program to test the above functions */
   
public static void main(String[] args)
    {
        BinaryTree tree =
new BinaryTree();
       
tree.root = new Node(1);
       
tree.root.left = new Node(2);
       
tree.root.right = new Node(3);
       
tree.root.left.left = new Node(7);
       
tree.root.left.right = new Node(6);
       
tree.root.right.left = new Node(5);
       
tree.root.right.right = new Node(4);
       
System.out.println("Spiral order traversal of Binary Tree is ");
       
tree.printSpiral(tree.root);
   
}
}

class Node
{
   
int data;
   
Node left, right;

    public
Node(int d)
    {
       
data = d;
       
left = right = null;
   
}
}

class BinaryTree
{
    Node
root;

   
/* print spiral order traversal of a tree  */
   
void printSpiral(Node node)
    {
       
boolean ltr = false;
       
ArrayList<Node> layer = new ArrayList<>();
       
layer.add(node);
        while
(layer.size() != 0)
        {
            printLevel(layer
,ltr);
           
layer = getNextLevel(layer);
           
ltr = !ltr;
       
}
    }

   
/* gets the next layer in the tree */
   
ArrayList<Node> getNextLevel(ArrayList<Node> node) {
        ArrayList<Node> nextLayer =
new ArrayList<>();
        for
(Node n:node) {
           
if(n.left != null)
                nextLayer.add(n.
left);
            if
(n.right != null) {
                nextLayer.add(n.
right);
            
}
        }
       
return nextLayer;
   
}

   
/* prints tree level taking direction into account */
   
void printLevel(ArrayList<Node> node, boolean ltr) {
       
if (ltr != true) {
            Collections.reverse(node)
;
       
}
       
for (Node n:node) {
            System.
out.print(n.data + " ");
       
}
    }
}