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

Question

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)

to use postorder() it will be

int preorder[6]={6,4,1,5,8,9};
int inorder[6]={1,4,5,6,8,9};
postorder( preorder,0,inorder,0,6);

out put will be

1 5 4 9 8 6

below is the incorrect code for print_preorder(), still not working below

void print_preorder( int inorder[], int inostart, int postorder[], int poststart, int length)
    {
      if(length==0) return; //terminating condition
      int i;
      for(i=inostart; i<inostart+length; i++)
        if(postorder[poststart+length-1]==inorder[i])
          break; 
      cout<<postorder[poststart+length-1]<<" ";
      print_preorder(inorder, inostart , postorder, poststart, i-inostart);
      print_preorder(inorder, inostart+i-poststart+1, postorder, i+1, length-i+inostart-1);
    }

Answer 1

Here's a few hints:

• The last element in the postorder subarray is your new preorder root.
• The inorder array can be split in two on either side of the new preorder root.
• You can call recursively call the print_preorder function on those two inorder subarrays.
• When calling the print_preorder function, the inorder and postorder arrays will be the same size.
• You have an out-of-bounds array access: postorder[poststart+length] is past the end of the array. To get the last element, you want postorder[poststart+length-1]
• Your first recursive print_preorder function chooses the wrong length. Remember that length is the length of the subarray, but inostart is the absolute position within the inorder array. Your function will probably call with a negative length.
• Your second recursive function is pretty far off for translating the bounds and length. It'll probably help to draw it on paper and trace your algorithm.

It may help to draw the tree:

     6
   /   \
  4     8
 / \     \
1   5     9

Then write out the three traversals:

// index:         0 1 2 3 4 5
int postorder[6]={1,5,4,9,8,6};
int inorder[6]=  {1,4,5,6,8,9};
int preorder[6]= {6,4,1,5,8,9};

Now, put down the computer, get out a pen & paper and think about the problem :)

Imagine this call stack (the new root is printed on the left):

6 print_preorder(len=6, in=[1 4 5 6 8 9], post=[1 5 4 9 8 6])
4 |-> print_preorder(len=3, in=[1 4 5], post=[1 5 4])
1 |   |-> print_preorder(len=1, in=[1], post=[1])
  |   |   |-> print_preorder(len=0, in=[], post=[])
  |   |   |-> print_preorder(len=0, in=[], post=[])
5 |   |-> print_preorder(len=1, in=[5], post=[5])
  |       |-> print_preorder(len=0, in=[], post=[])
  |       |-> print_preorder(len=0, in=[], post=[])
8 |-> print_preorder(len=2, in=[8 9], post=[9 8])
      |-> print_preorder(len=0, in=[], post=[])
9     |-> print_preorder(len=1, in=[9], post=[9])
          |-> print_preorder(len=0, in=[], post=[])
          |-> print_preorder(len=0, in=[], post=[])

Good luck :)

Answer 2

Im curious to see what the answer is did you figure it out? could you post your finished code?