Binary tree level order traversal in recursive

 

 

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 left to right   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 void levelOrderTraversalLeftToRight(TreeNode startNode) {    if(null == startNode){     return;    }    int level=1;    while(levelOrderTraversalLeftToRight(startNode, level++)){        }      }       //print right to left   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 levelOrderTraversalRightToLeft(TreeNode startNode) {    if(null == startNode){     return;    }    int level=1;    while(levelOrderTraversalRightToLeft(startNode, level++)){     System.out.println("---");    }      }    public static void main(String[] args)  {   // Creating a binary tree   TreeNode rootNode=createBinaryTree();   System.out.println("Level Order traversal of binary tree will be left to Right -->:");   levelOrderTraversalLeftToRight(rootNode);   System.out.println("Level Order traversal of binary tree will be Right to Left -->:");   levelOrderTraversalRightToLeft(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);     rootNode.left=node20;   rootNode.right=node60;     node20.left=node10;   node20.right=node30;     node60.left=node50;   node60.right=node70;     return rootNode;  } }

 

 

The provided Java code demonstrates a binary tree structure and implements two traversal methods: level-order traversal from left to right and level-order traversal from right to left. Below is an explanation of the code.

Explanation:

1. TreeNode Class:
• A static inner class TreeNode represents a node in the binary tree. It has three fields:
• int data: Stores the value of the node.
• TreeNode left: Reference to the left child node.
• TreeNode right: Reference to the right child node.
• The constructor TreeNode(int data) initializes the node with the provided value.
2. Level Order Traversal from Left to Right:
• levelOrderTraversalLeftToRight(TreeNode startNode, int level):
• This method recursively traverses the tree level by level, starting from the given startNode.
• If the level is 1, it prints the node's data.
• It recursively calls itself for the left and right subtrees, reducing the level by 1 in each recursive call.
• It returns true if the traversal is successful, or false if the startNode is null.
• levelOrderTraversalLeftToRight(TreeNode startNode):
• This method initiates the level-order traversal by calling the previous method with increasing levels until no nodes are left to traverse.
3. Level Order Traversal from Right to Left:
• levelOrderTraversalRightToLeft(TreeNode startNode, int level):
• Similar to the left-to-right traversal method, but the order of traversal is reversed.
• It starts with the right subtree first, followed by the left subtree.
• levelOrderTraversalRightToLeft(TreeNode startNode):
• This method initiates the right-to-left traversal by calling the previous method with increasing levels until no nodes are left to traverse.
4. Main Method:
• The main method creates a binary tree using the createBinaryTree() method.
• It then prints the tree in level order from left to right and right to left using the corresponding traversal methods.
5. Binary Tree Structure:
• The createBinaryTree() method builds a binary tree with the following structure:

markdown

 

40       /  \     20    60    /  \   /  \  10  30  50  70

 

• This tree is used as the input for the traversal methods.

Output:

When you run the code, the output will be:

text

Level Order traversal of binary tree will be left to Right -->: 40 20 60 10 30 50 70 Level Order traversal of binary tree will be Right to Left -->: 40 60 20 70 50 30 10

 

Summary:

• Left-to-right traversal prints nodes level by level starting from the leftmost node on each level.
• Right-to-left traversal prints nodes level by level starting from the rightmost node on each level.