Wednesday, September 28, 2011

Constructing Tree From Inorder and Preorder

ConstructTree(preorder, 0, preOrder.Length-1, inorder, 0, inorder.Length-1);
Node ConstructTree(int[] preorder, int ps, int pe, int[] inorder, int is, int ie)
{
  if(ps < pe || is < ie)
    return NULL;
  Node root = new Node();
  root->data = preorder[ps];
  int mid = is;
  while(inorder[mid] != preorder[ps]) 
    mid++;
  root->left = ConstructTree(preorder, ps+1, ps+mid-is, inorder, is, mid-1);
  root->right = ConstructTree(preorder, ps+mid-is+1, pe, inorder, mid+1, ie);
  return root;
}