Saturday, 22 August 2015

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.

ConstructBinaryTreeFromInOrderAndLevelOrderTraversal.java 
package com.javabypatel.tree;

public class ConstructBinaryTreeFromInOrderAndLevelOrderTraversal {
    private Node rootNode;

    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, 0,inOrder.length-1,0);
        System.out.println(rootNode);
    }

    private static Node constructTree(int[] levelOrder, int[] inOrder, int iStart, int iEnd, int lStart) {
        if (iStart > iEnd) {
            return null;
        }

        Node temp = null;
        int matchIndex = 0;
        for (int i=lStart; i<=levelOrder.length; i++) {
            for (int j=iStart; j<=iEnd; j++) {
                if (levelOrder[i] == inOrder[j]) {
                    temp = new Node(inOrder[j]);
                    matchIndex = j;
                    break;
                }
            }
            if (temp != null) {
                break;
            }
        }
        temp.setLeft(constructTree(levelOrder, inOrder, iStart, matchIndex-1, lStart+1));
        temp.setRight(constructTree(levelOrder, inOrder, matchIndex+1, iEnd, lStart+1));
        return temp;
    }
}
Node.java 
package com.javabypatel.tree;

public 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;
 }
}
Note:
For finding which element appear first in In-order array, we check each and every element of level order traversal in Inorder array. We can improve time complexity here.

 After breaking the in-order array in 2 parts, left and right, we can add all elements of Left/Right array in separate map and then check the same whether element is present in left/right tree in O(1) complexity

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

No comments:

Post a Comment