Construct Special Binary Tree from given Inorder traversal

Given Inorder Traversal of a Special Binary Tree in which key of every node is greater than keys in left and right children, construct the Binary Tree and return root.

Examples:

Input: inorder[] = {5, 10, 40, 30, 28}
Output: root of following tree
         40
       /   \
      10     30
     /         \
    5          28 

Input: inorder[] = {1, 5, 10, 40, 30, 
                    15, 28, 20}
Output: root of following tree
          40
        /   \
       10     30
      /         \
     5          28
    /          /  \
   1         15    20

Let the given array is {1, 5, 10, 40, 30, 15, 28, 20}. The maximum element in given array must be root. The elements on left side of the maximum element are in left subtree and elements on right side are in right subtree.

         40
      /       \  
   {1,5,10}   {30,15,28,20}

We recursively follow above step for left and right subtrees, and finally get the following tree.

          40
        /   \
       10     30
      /         \
     5          28
    /          /  \
   1         15    20

Algorithm: buildTree()
1) Find index of the maximum element in array. The maximum element must be root of Binary Tree.
2) Create a new tree node ‘root’ with the data as the maximum value found in step 1.
3) Call buildTree for elements before the maximum element and make the built tree as left subtree of ‘root’.
5) Call buildTree for elements after the maximum element and make the built tree as right subtree of ‘root’.
6) return ‘root

Solution:

public class ConstructTreefromInOrder {

static Node root;

public static void main(String[] args) {

ConstructTreefromInOrder tree=new ConstructTreefromInOrder();

int[] in=new int[]{5, 10, 40, 30, 28};

Node treeNode=constructTree(in,0,in.length-1,tree.root);

System.out.println("Inorder traversal");

callInOder(treeNode);

}

private static void callInOder(Node treeNode) {

if(treeNode==null)

return;

callInOder(treeNode.left);

System.out.println(" "+treeNode.data);

callInOder(treeNode.right);

// TODO Auto-generated method stub

}

private static Node constructTree(int[] in, int start, int end, Node root2) {

if(start>end)

return null;

int index=getRootIndex(in,start,end);

root2=new Node(in[index]);

if(start==end)

return root2;

root2.left=constructTree(in, start, index-1, root2.left);

root2.right=constructTree(in, index+1, end, root2.right);

// TODO Auto-generated method stub

return root2;

}

private static int getRootIndex(int[] in, int start, int end) {

int max=in[start];

int index=start;

for(int i=start+1;i<=end;i++)

{

if(in[i]>max)

{

max=in[i];

index=i;

}

}

// TODO Auto-generated method stub

return index;

}

}