Spiral order traversal of a tree - Java

public class TreeTraversal {
public static void main(String[] args) {
Node node = new Node(40);
node.left = new Node(35);
node.right = new Node(50);
node.left.left = new Node(30);
node.left.right = new Node (38);
node.left.left.right = new Node(33);
node.left.left.left = new Node(28);
spiralOrder(node);
}

public static void spiralOrder(Node root){
if (root == null) return;
boolean dir = false;
int height = height(root);
for (int i = 1; i <= height; i++) {
printSpiralLevelOrder(root, i, dir);
dir = !dir;
}
}

public static void printSpiralLevelOrder(Node root, int level, boolean dir){
if(root == null) return;
if(level == 1) System.out.print(root.value);
else if(level > 1){
if(dir){
printSpiralLevelOrder(root.left, level-1, dir);
printSpiralLevelOrder(root.right, level-1, dir);
} else {
printSpiralLevelOrder(root.right, level-1, dir);
printSpiralLevelOrder(root.left, level-1, dir);
}
}
}

public static int height(Node node) {
if(node == null) return 0;

int lHeight = height(node.left);
int rHeight = height(node.right);

if(lHeight > rHeight)
return lHeight + 1;
else
return rHeight + 1;
}
}


class Node{
Node left;
Node right;
int value;

public Node(int value){
this.value = value;
}
}

Comments

Popular posts from this blog

public vs protected vs default access modifiers - Java

Class, Reference and Object