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 integer array. How do I similarly 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

1. The last element in post order will be the root of the tree.

2. After that we will look in Inorder array to determine the position of the root. left side of the array is left sub tree and right side is right sub tree.

3. By using that index we shall determine the element in left which is the root.

4. similarly we do for the right sub tree, The main idea is we determine the indexes of left sub tree and right sub tree by looking in inorder array. hope i was clear..

   public static void printpreorder(char []inorder,int i_start,int i_end,char[] postorder,int p_start,int p_end)
   {
     if(i_start > i_end || p_start > p_end)
            return ; 
     char root = postorder[p_end];
     System.out.print(root);
     System.out.print("(");
       int k=0;
         for(int i=0; i< inorder.length; i++){
             if(inorder[i]==root){
               k = i;
               break;
             }
         }
     printpreorder(inorder, i_start, k-1, postorder, p_start, p_start+k-(i_start+1));
     System.out.print(")(");
     printpreorder(inorder, k+1, i_end, postorder, p_start+k-i_start, p_end-1);
     System.out.print(")");    
   }
   

This was hommework for me. Thanks to @Stephen for a good answer

Answer 2

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 :)