Construct a Binary Tree from In-order and Level-order traversals.


How to construct a Binary Tree from given In order and Level order traversals.



Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
Two traversals are given as input,

        int[] inOrder =    { 4, 2, 6, 5, 7, 1, 3 };
        int[] levelOrder = { 1, 2, 3, 4, 5, 6, 7 };


By using above 2 given In order and Level Order traversal, construct Binary Tree like shown below,




First let us understand what does In order and Level order traversal mean?



Level order traversal is traversing a Tree level by level and hence the level order traversal of above tree is ,
Level order traversal : 1   2   3   4   5   6   7.

From the above example, we can see that first element (in our case array value 1) of Level order traversal is always a root node of a Tree as Root Node is present at Level 1 and hence read first.


In order traversal is traversing a Tree in which Left Node is read first, then root node and then right node and hence the In order traversal of above tree is,
In order traversal : 4   2   6   5   7   1   3.

From the above example, we can see that 
Root element will be present somewhere at the middle in In-order traversal 
(4, 2, 6, 5, 7, 1, 3)
(since Left nodes of a Tree are read first, then Root Node and then Right nodes).


So root node will be present somewhere at middle, but by simply looking at given In order traversal it is not possible to identify which element is root element as we are not aware of exact position.

More details on In Order and Level Order traversal: In Order and Level Order Traversal.

Algorithm


We just saw that first element of Level order traversal is root node.

Step 1:
Read the first element from Level order traversal which is root node.
Now, we come to know which is root node.(in our case it is 1)

Step 2: 
Search the same element (element 1) in In-order traversal, 
when the element is found in In-order traversal, then we can very well say that all the elements present before the node found are Left children/sub-tree and all the elements present after the node found are Right children/sub-tree of node found. (as in In-order traversal Left child's are read first and then root node and then right nodes.)

In our example,  
(4, 2, 6, 5, 7)  will be part of Left Sub-tree of Node 1.
(3) will be part of Right Sub-tree of Node 1.

Now we got the fresh inOrder array (4, 2, 6, 5, 7)  and (3)
Repeat the  Step 1 and Step 2 for new inOrder arrays.


So, keeping the above rule in mind, 
We will find the root node from Level-order traversal and then left child's and right child's from In-order traversals like shown below,



So if we repeat the process, we will get our Binary Tree ready.
See image below for detailed explanation,



Java Program to construct a Binary Tree from given Inorder and Level order traversals.



class Node{
 private int data;
 private Node left;
 private Node right;
 private Node nextRight;

 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;
 }
 public Node getNextRight() {
  return nextRight;
 }
 public void setNextRight(Node nextRight) {
  this.nextRight = nextRight;
 }
} 


ConstructBinaryTreeFromInOrderAndLevelOrderTraversal.java

package tree;

public class ConstructBinaryTreeFromInOrderAndLevelOrderTraversal {

 public static void main(String args[]) {
  int[] inOrder =    { 4, 2, 6, 5, 7, 1, 3 };
  int[] levelOrder = { 1, 2, 3, 4, 5, 6, 7 };

  Node rootNode = constructTree(levelOrder, inOrder);
  System.out.println(rootNode);
 }

 private static Node constructTree(int[] levelOrder, int[] inOrder){
  Node startNode=null;
  return constructBinaryTree(startNode, levelOrder, inOrder, 0, inOrder.length-1);
 }
 
 private static Node constructBinaryTree(Node startNode, int[] levelOrder, int[] inOrder, int inStart, int inEnd) {
  
  // this condition is true when no more element to work that is we reach end of left or right.
  if(inStart>inEnd){ 
   return null;
  }

  // this condition is true when we are working on last element present either on left or right.
  if(inStart==inEnd){
   return new Node(inOrder[inStart]);
  }

  // Finding which elements in inOrder array appear first in levelOrder array.
  // What actually we are doing here is, picking the element from levelOrder array and 
  // finding where that element is found in inOrder array and once found we will get to know
  // left and right child's as well for next recursive call.
  boolean isFound = false;
  int index=0; // it represents the index in inOrder array of element that appear first in levelOrder array.
  for (int i = 0; i < levelOrder.length-1; i++) {
   int data = levelOrder[i];
   for (int j = inStart; j < inEnd; j++) {
    if(data==inOrder[j]){
     startNode = new Node(data);
     index = j;
     isFound = true;
     break;
    }
   }
   if(isFound){
    break;
   }
  }

  //elements present before index are part of left child's of startNode.
  //elements present after index are part of right child's of startNode.
  startNode.setLeft(constructBinaryTree(startNode, levelOrder, inOrder, inStart, index-1));
  startNode.setRight(constructBinaryTree(startNode, levelOrder, inOrder, index+1, inEnd));

  return startNode;
 }

}



If you find any issue in post or face any error while implementing, Please comment.

Post a Comment