Building a Binary Tree using Inorder and Preorder Traversals in Java

This is a well known problem where given any two traversals of a tree  such as inorder & preorder or inorder & postorder traversals we need to rebuild the tree.

The following algorithm demonstrates how to rebuild a binary tree from given inorder and preorder traversals:

Global Declarations
preIndex=0;
Structure tNode
{
int data;
tNode left=null;
tNode right=null;
}

Main
1. Set Inorder and Preorder traversals
2. startNode = buildTree(0, in.length-1)
3. printPreorder(startNode)
4. printInorder(startNode)
5. printPostorder(startNode)
6. Stop

buildTree(inStart, inEnd)
1. If (inStart>inEnd)
return NULL
   End If
2. Create a new tree node tNode with tNode.data = preorder[preIndex].
3. Increment a preIndex Variable to pick next element in next recursive call.
4. If(inStart == inEnd)
return tNode
   End If
5. Find the picked element’s index in Inorder. Let the index be inIndex.
6. tNode.left = buildTree (inStart, inIndex-1)
7. tNode.right = buildTree ( inIndex+1, inEnd)
8. return tNode.

Now consider the following example:

Preorder Traversal:    1    2    4    8    9    10    11    5    3    6    7

Inorder Traversal:       8    4    10    9    11    2    5    1    6    3    7

Iteration 1:

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

Root – {1}

Left Subtree – {8,4,10,9,11,2,5}

Right Subtree – {6,3,7}

We recursively follow above steps and get the following tree.

Iteration 2:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}

Root – {3} Left Subtree – {6} Right Subtree – {7}

Iteration 3:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}		Root – {3} Left Subtree – {6} Right Subtree – {7}
Root – {4} Left Subtree – {8} Right Subtree – {10,9,11}	Done	Done

Iteration 4:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}			Root – {3} Left Subtree – {6} Right Subtree – {7}
Root – {4} Left Subtree – {8} Right Subtree – {10,9,11}		Done	Done
Done	R – {9} Left ST – {10} Right ST-{11}	Done	Done

Finally a program in Java to demonstrate this tree building using traversal paths.

class TNode
{
 int data;
 TNode left;
 TNode right;

 TNode(int d)
 {
  data = d;
  left= null;
  right=null;
 }
}

class TreeBuilder
{
 static int preIndex;
 static int[] in, pre;
 TNode Start;

 static void setValue(int[] i, int[] p)
 {
  in = i;
  pre = p;
  preIndex=0;
 }

 static int findInIndex(int inStart, int inEnd, int value)
 {
  for(int i=inStart; i<=inEnd; i++)
   if(in[i]==value)
   return i;

  return -1;
 }


 //Main method with the logic for building tree using Pre and Inorder traversals
 static TNode buildTree(int inStart, int inEnd)
 {
  if(inStart>inEnd)
   return null;

  TNode node = new TNode(pre[preIndex++]);

  if(inStart==inEnd)
   return node;

  int inIndex = findInIndex(inStart, inEnd, node.data);

  node.left=buildTree(inStart, inIndex-1);
  node.right=buildTree(inIndex+1, inEnd);

  return node;
 }
}

class TreeBuilderDemo 
{
 public static void main(String[] args) 
 {
  int[] in = {8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7};
  int[] pre = {1, 2, 4, 8, 9, 10, 11, 5, 3, 6, 7};

  TreeBuilder.setValue(in, pre);

  TNode start = TreeBuilder.buildTree(0,in.length-1);


  //Now we will traverse through the newly created tree to verify that it is proper
  System.out.print("\nPreorder\t: ");
  printPreorder(start);

  System.out.print("\n\nInorder\t\t: ");
  printInorder(start);

  System.out.print("\n\nPostorder\t: ");
  printPostorder(start);

  System.out.println("");
 }

 static void printInorder(TNode node)
 {
  if (node == null)
   return; 

  printInorder(node.left);   
  System.out.print(node.data + "\t "); 
  printInorder(node.right);   
 }

 static void printPreorder(TNode node)
 {
  if (node == null)
   return; 

  System.out.print(node.data + "\t ");
  printPreorder(node.left);    
  printPreorder(node.right);   
 }

 static void printPostorder(TNode node)
 {
  if (node == null)
   return; 

  printPostorder(node.left);   
   printPostorder(node.right);   
  System.out.print(node.data + "\t ");
 }
}

Output of the program