Process: 1>It is working as pre-order traversal binary tree. So all data should be printed at level 1 place2>It is like as toggling or flip flop the left and right
package com.kartik.org;
public class BinaryTreeLevelOrder {
public static class TreeNode
{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
}
}
// prints in level order
public static boolean levelOrderTraversalLeftToRight(TreeNode startNode,int level) {
if(null == startNode){
return false;
}
if(level == 1){
System.out.println(startNode.data+" ");
return true;
}
boolean left =levelOrderTraversalLeftToRight(startNode.left, level-1);
boolean right =levelOrderTraversalLeftToRight(startNode.right, level-1);
return left || right;
}
public static boolean levelOrderTraversalRightToLeft(TreeNode startNode,int level) {
if(null == startNode){
return false;
}
if(level == 1){
System.out.println(startNode.data+" ");
return true;
}
boolean right =levelOrderTraversalRightToLeft(startNode.right, level-1);
boolean left =levelOrderTraversalRightToLeft(startNode.left, level-1);
return right || left;
}
public static void levelOrderTraversalZigZagBinaryTree(TreeNode startNode) {
if(null == startNode){
return;
}
int level=1;
while(levelOrderTraversalLeftToRight(startNode, level++) && levelOrderTraversalRightToLeft(startNode, level++)){
}
}
public static void main(String[] args)
{
// Creating a binary tree
TreeNode rootNode=createBinaryTree();
System.out.println("Level Order traversal in Zig zag binary tree will be -->:");
levelOrderTraversalZigZagBinaryTree(rootNode);
}
public static TreeNode createBinaryTree()
{
TreeNode rootNode =new TreeNode(40);
TreeNode node20=new TreeNode(20);
TreeNode node10=new TreeNode(10);
TreeNode node30=new TreeNode(30);
TreeNode node60=new TreeNode(60);
TreeNode node50=new TreeNode(50);
TreeNode node70=new TreeNode(70);
TreeNode node55=new TreeNode(55);
TreeNode node5=new TreeNode(5);
rootNode.left=node20;
rootNode.right=node60;
node20.left=node10;
node20.right=node30;
node60.left=node50;
node60.right=node70;
node50.right=node55;
node10.left=node5;
return rootNode;
}
}
Level Order traversal in Zig zag binary tree will be -->: 40 60 20 10 30 50 70 55 5
If you find this post helpful, I would really appreciate if you can share it with your friends. Also you can check more questions and analysis here.
I am Kartik Chandra Mandal from Bangalore, India. Working as software engineer in Java technology. Have good knowledge of OWASP and CSRF in security for applications and it's implementation in Java technology.