Header Ads Widget

Responsive Advertisement

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.

 


Binary tree level order traversal in recursive
Binary tree level order traversal in recursive




Post a Comment

0 Comments