Construct Binary Search Tree From In Order and Pre 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 ConstructBSTFromInorderAndPreOrderTraversal {
 public static void main(String[] args) {
  new ConstructBSTFromInorderAndPreOrderTraversal();
 }
 
 public ConstructBSTFromInorderAndPreOrderTraversal() {
  int inorder[] = {20, 30, 35, 40, 45, 50, 55, 60, 70};
  int preorder[] = {50, 40, 30, 20, 35, 45, 60, 55, 70};
  
  Node n = constructTree(inorder, 0, inorder.length-1, preorder, 0, preorder.length-1);
  System.out.println(n);
 }

 private Node constructTree(int[] inorder, int inStart, int inEnd, int[] preorder, int preStart, int preEnd) {
  if(inStart>inEnd || preStart>preEnd)
   return null;

  Node n = new Node(preorder[preStart]);

  //Search index in Inorder array
  int i = inStart;
  for (; i < inEnd; i++) {
   if(preorder[preStart] == inorder[i]){
    break;
   }
  }
  //Now wherever i has stopped that is the index we got matching element in inorder array.
  //We come to now in INORDER array, element at index i is Node and elements at (i-1) is left part of Tree and elements at (i+1) is right part of tree.
  //In Next iteration what portion of preorder array to be considered is a question,

  int length = i - inStart; 
  //This is not a index that we need to consider for preorder preEnd but is simply calculating length that this(length) many 
  //number of elements to cover from preStart, it is actually a count of elements to cover.
  //So in preorder first is always node(which we consider in first iteration), 
  //so always in next iteration we are decreasing the amount of array to consider by 1 that is why (preStart+1) is starting point.
  //and ending point for preorder is, preEnd is (preStart+1) as starting point and add number of 
  //elements we got as length(which gives us how many count of numbers to consider), actually, (length-1) and not length 
  //because we already cover element at length where we stopped i.

  //For Left side,
  //instart and inEnd to construct is very easy, but for preorder, carefully select start and end of preorder,
  //preStart is (preStar+1) because, everytime it visit left, that node is covered, so for next iteration on left side move it should be +1 that is why (preStart+1)
  //preEnd is (preStart+length) because we need to first calculate how many number of elements to include that we will get from length 
  //but from where exactly to start is from prestart + number of elements ie length ie preStart+length.  
  n.setLeft(constructTree(inorder, inStart, i-1, preorder, preStart+1, preStart+length));
  
  //For Right side, 
  //inStart and inEnd is understood.
  //for preStart on right side is very important, because that will be going to be root of right side, 
  //for left side your preEnd is (preStart+length), so your right side start will be +1 of that as (preStart+length) index will be covered on left side.
  n.setRight(constructTree(inorder, i+1, inEnd, preorder, preStart+length+1, preEnd));
  return n;
 }


}