Answer: Trees

Question: Write a function that prints the postorder traversal of a binary tree given a preorder and inorder traversal of the tree. This function need not actually construct the tree, just print it. Its prototype will be

void printPostOrder(int *inorder, int *preorder, int num_nodes);

Answer:

void
printPostOrder(int *inorder, int *preorder, int n) {
    // base case: the tree is empty
    if(n == 0) return;

    // compute position of root in inorder traversal
    int root_pos;
    for(root_pos = 0; inorder[root_pos] != preorder[0]; root_pos++);

    // print postorder for the left subtree
    printPostOrder(inorder, preorder + 1, root_pos);

    // print postorder for the right subtree
    printPostOrder(inorder + root_pos + 1, preorder + root_pos + 1,
        n - root_pos - 1);
    
    // print the root
    cout << preorder[0] << endl;
}