This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Wednesday, 24 December 2014

Construct Binary Search Tree From Given In Order and Post Order Traversal

package tree;

public class Node{
 
 private Node left;
 private Node right;
 private int data;
 
 public Node(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 int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }
}


package tree;

/*    
              50
              /\
           40    60
           /\    /\
         30  45 55 70
         /\
       20  35

 */

public class ConstructBSTFromInorderAndPostOrderTraversal {
 public static void main(String[] args) {
  new ConstructBSTFromInorderAndPostOrderTraversal();
 }

 public ConstructBSTFromInorderAndPostOrderTraversal() {
  int inorder[] = {20, 30, 35, 40, 45, 50, 55, 60, 70};
  int postorder[] = {20, 35, 30, 45, 40, 55, 70, 60, 50};

  int inStart = 0;
  int inEnd = inorder.length-1;
  int postStart =0;
  int postEnd = postorder.length-1;

  Node n = buildTree(inorder, inStart, inEnd, postorder, postStart, postEnd);
  System.out.println(n);
 }

 public Node buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd){
  if(inStart > inEnd || postStart > postEnd)
   return null;

  int rootValue = postorder[postEnd];
  Node root = new Node(rootValue);

  int k=0;
  for(int i = inStart; i <= inEnd; i++){
   if(inorder[i]==rootValue){
    k = i;
    break;
   }
  }

  int len = k - inStart;
  root.setLeft(buildTree(inorder, inStart, k-1, postorder, postStart, postStart+len-1));
  root.setRight(buildTree(inorder, k+1, inEnd, postorder, postStart+len, postEnd-1));    
  return root;
 }
}

No comments:

Post a Comment