Construct tree from inorder and preorder traversal

Reference :-
http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

Problem Statement :-
Construct binary tree from inorder and preorder traversal
Let us consider the below traversals:

Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.

                 A
               /   \
             /       \
           D B E     F C
We recursively follow above steps and get the following tree.

         A
       /   \
     /       \
    B         C
   / \        /
 /     \    /
D       E  F
Algorithm: buildTree()
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.

My java implementation :-

import java.util.ArrayList;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

class TreeNode {
  
    // data members
public int key;
public char charkey;
    public TreeNode left;
    public TreeNode right;
  
    // Constructor
    public TreeNode(int key) { this.key = key; left = null; right = null; }
    public TreeNode(char charkey) { this.charkey = charkey; left = null; right = null; }
  
    // Methods to set left and right subtrees
    public void setLeft(TreeNode left)   { this.left = left; }
    public void setRight(TreeNode right) { this.right = right; }
    
    public static void printLevelOrder(TreeNode root)
    {
      Queue<TreeNode> queue = new LinkedBlockingQueue<TreeNode>(); 
      
      while(root != null){
     System.out.println(root.charkey);
     if(root.left!=null){
     queue.add(root.left);
     }
     if(root.right!=null){
     queue.add(root.right);
     }
     root = queue.poll();
      }
    }
}


 class ConstructTreeFromTraversal {
 
int preOrderIndex=0;
String inorder, preorder;

public static void main(String[] args) {

ConstructTreeFromTraversal obj = new ConstructTreeFromTraversal();
obj.inorder="DBEAFC";
obj.preorder="ABDECF";
TreeNode root = obj.constructTree();
System.out.println("Printing Level order traversal");
TreeNode.printLevelOrder(root);
System.out.println("Done");
}

public TreeNode constructTree(){
TreeNode root = constructTree_internal(inorder);
return root;

}
public TreeNode constructTree_internal(String inorder){
if(inorder.equals("")){
return null;
}
// preOrderIndex which is initialized as zero indicates current position in preorder
// that is to be considered as root
char rootKey = preorder.charAt(preOrderIndex);
preOrderIndex++;
TreeNode root = new TreeNode(rootKey);
// See it length of inorder is more than 1 i.e. it has node other than root
if(inorder.length()>1){
// Find rootKey in inOrder and split it into two parts
String [] child = inorder.split(rootKey+"");
try{
TreeNode leftChild = constructTree_internal(child[0]);
root.setLeft(leftChild);
// Call if right nodes are present
if(child.length>1){
TreeNode rightChild = constructTree_internal(child[1]);
root.setRight(rightChild);
}
}catch (Exception e){
e.printStackTrace();
}
}
return root;
}

}

Output

Printing Level order traversal

A

B

C

D

E

F

Done