Monday, August 17, 2015

Construct Tree from PreOrder & InOrder

Problem 

Construct a tree from pre-order and in-order traversal arrays.
What I learnt here? - Arrays.copyOfRange(int[], int start, int end) copies from start (included) till end-1 (i.e. exclusive of end)

Solution

import java.util.Arrays;
public class TreeProblem2 {
 class Tree {
  int node;
  Tree left;
  Tree right;
 }
 
 int preIndex = 0;
 Tree construct(int[] pre, int[] in) {
  if(preIndex >= pre.length  || in.length==0) return null;

  Tree t= new Tree();
  t.node = pre[preIndex++]; //first element in preorder is the root

  //Get pos of root in the inorder. 
  //Elements left of that will be the left tree
  //Elements to the right of that will be the right tree
  int i =0;
  for(;i< in.length; i++){
   if(in[i] == t.node) break;
  }

  int[] leftIn = Arrays.copyOfRange(in, 0, i);
  int[] rightIn = Arrays.copyOfRange(in, i+1, in.length);

  t.left = construct(pre, leftIn);
  t.right = construct(pre, rightIn);
  return t;
 }

 public static void main(String[] args) {
  int[] pre = {10,5,80,9,2,6};
  int[] in = {80,5,9,10,6,2};
  TreeProblem2 ob = new TreeProblem2();
  Tree t = ob.construct(pre, in);
  TreeOperations.printTree(t);
 }
}

No comments:

Post a Comment