Make a Binary Tree from Given Inorder and Preorder Traveral.

Objective: Given a inorder and preorder traversal, construct a binary tree from that.

Input: Inorder and preorder traversals

Similar Problem: Construct a binary tree from given Inorder and Postorder Traversal

Approach:

int [] inOrder = {2,5,6,10,12,14,15};

int [] preOrder = {10,5,2,6,14,12,15};

    • First element in preorder[] will be the root of the tree, here its 10.
    • Now the search element 10 in inorder[], say you find it at position i, once you find it, make note of elements which are left to i (this will construct the leftsubtree) and elements which are right to i ( this will construct the rightSubtree).
    • See this step above and recursively construct left subtree and link it root.left and recursively construct right subtree and link it root.right.

  • See the picture and code.
Make-a-Binary-Tree-from-Given-Inorder-and-Preorder-Traveral
Make-a-Binary-Tree-from-Given-Inorder-and-Preorder-Traveral

Complete Code:

public class MakeTreefromInorderAndPreorder {
public static int pIndex=0;
public Node makeBTree(int [] inOrder, int [] preOrder, int iStart, int iEnd ){
if(iStart>iEnd){
return null;
}
Node root = new Node(preOrder[pIndex]);pIndex++;
if(iStart==iEnd){
return root;
}
int index = getInorderIndex(inOrder, iStart, iEnd, root.data);
root.left = makeBTree(inOrder,preOrder,iStart, index1);
root.right = makeBTree(inOrder,preOrder,index+1, iEnd);
//}
return root;
}
public int getInorderIndex(int [] inOrder, int start, int end, int data){
for(int i=start;i<=end;i++){
if(inOrder[i]==data){
return i;
}
}
return 1;
}
public void printINORDER(Node root){
if(root!=null){
printINORDER(root.left);
System.out.print(" " + root.data);
printINORDER(root.right);
}
}
public static void main (String[] args) throws java.lang.Exception
{
int [] inOrder = {2,5,6,10,12,14,15};
int [] preOrder = {10,5,2,6,14,12,15};
MakeTreefromInorderAndPreorder i = new MakeTreefromInorderAndPreorder();
Node x = i.makeBTree(inOrder, preOrder, 0, inOrder.length1);
System.out.println("Constructed Tree : ");
i.printINORDER(x);
}
}
class Node{
int data;
Node left;
Node right;
public Node (int data){
this.data = data;
left = null;
right = null;
}
}

Output:

Constructed Tree : 
  2  5  6  10  12  14  15

2 thoughts on “Make a Binary Tree from Given Inorder and Preorder Traveral.”

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.