Level order traversal in spiral form OR
Printing a Binary Tree in Zig Zag Level-Order OR
Print a binary tree in Zig Zag way.
Given a binary tree, write a program to print nodes of the tree in spiral order. You can also say it as Spiral order traversal of a tree. Let us first understand what we want to achieve? what is the input and what will be the expected output?
See below image for better understanding the problem statement.
Note:
If you observe Zig Zag Traversing is very similar to Level order traversal with few modification.
So first let's understand how to travel a Binary Tree in Level Order.
Level order traversal of Tree shown in Case 1 is 20 4 10 8 5.
Level order traversal of Tree shown in Case 2 is 20 4 10 8 5 2 1.
For more details on Level order traversal, Please refer : Level order traversal
Algorithm
- Take 2 Stack, one for current level and one for next level.
- For filling the next Level stack, we have to see whether it need to be filled Left to Right or Right to left as we are reading the Level Order spirally.
- When we are reading current level stack, all the children's of current level stack will go to next level stack.
- When current level stack has no value and is Empty at that time point current level stack reference to hold next level stack values, that is current level stack will now point to next level stack and next level stack should be reinitialize for its next level. Also, this is the time when we need to alter our reading style for childrens that is it need to be read in left - right fashion.
Java Program for reading a Binary Tree in Spiral way.
ZigZagTreeTraversal.java
package javabypatel.tree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class ZigZagTreeTraversal {
private Node rootNode;
public static void main(String[] args) {
new ZigZagTreeTraversal();
}
public ZigZagTreeTraversal(){
addNode(rootNode, 1);
addNode(rootNode, 2);
addNode(rootNode, 3);
addNode(rootNode, 4);
addNode(rootNode, 5);
addNode(rootNode, 6);
addNode(rootNode, 7);
addNode(rootNode, 8);
addNode(rootNode, 9);
addNode(rootNode, 10);
addNode(rootNode, 11);
zigZagTraverse(rootNode);
}
private void zigZagTraverse(Node rootNode) {
if(rootNode==null){
return;
}
Stack<Node> currentLevelStack = new Stack<Node>();
Stack<Node> nextLevelStack = new Stack<Node>();
boolean isLeftRightReading = true;
currentLevelStack.add(rootNode);
while(!currentLevelStack.isEmpty()){
Node n = currentLevelStack.pop();
System.out.print(n.getData() + " ");
if(isLeftRightReading){
if(n.getLeft()!=null)
nextLevelStack.push(n.getLeft());
if(n.getRight()!=null)
nextLevelStack.push(n.getRight());
}else{
if(n.getRight()!=null)
nextLevelStack.push(n.getRight());
if(n.getLeft()!=null)
nextLevelStack.push(n.getLeft());
}
if(currentLevelStack.isEmpty()){
isLeftRightReading = !isLeftRightReading;
currentLevelStack=nextLevelStack;
nextLevelStack = new Stack<Node>();
}
}
}
private void addNode(Node rootNode, int data){
//First check is there any Nodes present.
if(rootNode==null){
// No Nodes are Present, create one and assign it to startNode
Node temp1=new Node(data);
this.rootNode=temp1;
}else{
//Nodes present, So check the proper position where to add New Node.
//Checking whether Left child and Right child are present for root Node.
if(rootNode.getLeft()!=null && rootNode.getRight()!=null){
//Left and Right Child exist, Also, we need to add new Node in Sequential Fashion of Left and Right,
//We have to scan all Levels one by one to check a proper place for new Node.
//Also, we for each and every node we need to check whether Left and Right Exist,
//So we need to store them for later Processing that is why we introduced Queue.
Queue<Node> queue = new LinkedList<Node>();
queue.add(rootNode);
while(!queue.isEmpty()){
Node obj = (Node)queue.poll();
if(obj.getLeft()!=null && obj.getRight()!=null){
queue.add(obj.getLeft());
queue.add(obj.getRight());
}else if(obj.getLeft()==null){
Node temp1=new Node(data);
obj.setLeft(temp1);
break;
}else{
Node temp1=new Node(data);
obj.setRight(temp1);
break;
}
}
}else{
// We reach this condition when either Left or Right is Null, but not sure which side is Null.
if(rootNode.getLeft()==null){
Node temp1=new Node(data);
rootNode.setLeft(temp1);
}else{
Node temp1=new Node(data);
rootNode.setRight(temp1);
}
}
}
}
}
Node.java
package javabypatel.tree;
public class Node{
private int data;
private Node left;
private Node right;
public Node(int data) {
this.data=data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
Reading a Binary Tree in Zig Zag way from Bottom to up.
What do I mean by reading a binary tree in reverse Zig Zag way is,
So how to read in reversed zig zag fashion?
We just saw how to read in Zig Zag fashion from Top to bottom, instead of printing the result every time, if we collect it in some variable say zigZagTreeReadOutput, then what we get for above tree is,
String zigZagTreeReadOutput = "20,10,4,8,5,2,1"
Now, for finding the reversed ZigZag traversal of same tree, we can simply reverse the result of Top down Zig Zag traversal record.
So we will get, 1,2,5,8,4,10,20
You may also like to see
Find Kth SMALLEST element in BST(Binary Search Tree)
Check whether Binary Tree is foldable or not.
Check if two nodes are cousins in a Binary Tree.
Get Level/Height of node in binary tree
Print nodes at K distance from Leaf node in Binary tree.
Construct a Binary Tree from In-order and Post-order traversals.
Print Nodes in Top View of Binary Tree.
check if two binary trees are identical or not.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment