Sorted Linked List To Balanced BST

http://www.geeksforgeeks.org/archives/17063

Construct binary tree given its inorder and preorder traversal

Construction of Binary tree given its inorder and preorder traversal.

 public static Node construct(String preorder, String inorder, int start, int end, int [] preorderIndex)
 {
  if(start > end)
   return null;
  
  Node root = new Node(preorder.charAt(preorderIndex[0]));
  
  ++preorderIndex[0];
  
  int inorderIndex = inorder.indexOf(""+root.data);
  
  root.left  = construct(preorder, inorder, start, inorderIndex - 1, preorderIndex);
  root.right = construct(preorder, inorder, inorderIndex + 1, end, preorderIndex);
  
  return root;
 }
  
 public static void main(String[] args) {
  
  String preorder = "ABCDEFG";
  String inorder  = "GFEDCBA";
  
  // We use this as a reference object, so that we pick the correct value from preorder array during
  // recursion. This could be done by having a static variable as well.
  int [] preorderIndex = new int[1];
  
  Node root = CodeSamples.construct(preorder, inorder, 0, preorder.length() - 1, preorderIndex);
                // Verify if it build correctly
  BinaryTree.preorderTraversal(root);
  System.out.println();
  BinaryTree.inorderTraversal(root);
  
 }

For explanation of the approach and other ways of doing it, visit this link: http://www.geeksforgeeks.org/archives/6633