How do I output the preorder traversal of a tree given the inorder and postorder tranversal?

Posted by user342580 on Stack Overflow See other posts from Stack Overflow or by user342580
Published on 2010-06-08T23:57:46Z Indexed on 2010/06/09 0:02 UTC
Read the original article Hit count: 250

Given the code for outputing the postorder traversal of a tree when I have the preorder and the inorder traversal in an interger array. How do I similarily get the preorder with the inorder and postorder array given?

void postorder( int preorder[], int prestart, int inorder[], int inostart, int length)
{ 
  if(length==0) return; //terminating condition
  int i;
  for(i=inostart; i<inostart+length; i++)
    if(preorder[prestart]==inorder[i])//break when found root in inorder array
      break;
  postorder(preorder, prestart+1, inorder, inostart, i-inostart);
  postorder(preorder, prestart+i-inostart+1, inorder, i+1, length-i+inostart-1);
  cout<<preorder[prestart]<<" ";
}

Here is the prototype for preorder()

void preorder( int inorderorder[], int inostart, int postorder[], int poststart, int length)

© Stack Overflow or respective owner

Related posts about c++

Related posts about homework