Practice Exercise

Postfix Traversal of a BST

Your task is to write a function, bstPostfix, that prints out the values of the given BST in postfix order. The values should be printed out space-separated on a single line.

Assumptions and Constraints

You must not modify the given tree.

Download

While in your practice exercises directory, run the following command:

unzip /web/cs2521/practice-exercises/trees/bstPostfix/downloads/bstPostfix.zip

If you're working at home, download bstPostfix.zip by clicking on the above link and then unzip the downloaded file.

Files

bst.c	Contains code for reading and printing a BST
bst.h	Contains the definition of the BST data structure and function prototypes
testBstPostfix.c	Contains the main function, which reads in a BST from standard input and calls `bstPostfix`
bstPostfix.c	Contains `bstPostfix`, the function you must implement
Makefile	A makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic tests
autotest	A script that uses the tests in the tests directory to autotest your solution. You should only run this after you have tested your solution manually.

Examples

./testBstPostfix
Enter the preorder traversal of the BST: 

BST:

X

Values in postfix order:

./testBstPostfix
Enter the preorder traversal of the BST: 8 7 4 2 1 3 6

BST:

        8
       /
      7
     /
    4
   / \
  2   6
 / \
1   3

Values in postfix order: 1 3 2 6 4 7 8

./testBstPostfix
Enter the preorder traversal of the BST: 7 4 3 1 10 8 13

BST:

       7
      / \
     /   \
    4    10
   /     / \
  3     8  13
 /
1

Values in postfix order: 1 3 4 8 13 10 7

Testing

You can compile and test your function using the following commands:

make                                 # compiles the program
./testBstPostfix                  # tests with manual input, outputs to terminal
./testBstPostfix < input-file     # tests with input from a file, outputs to terminal
./testBstPostfix < tests/01.in    # for example, tests with input from tests/01.in
                                       # (then manually compare with tests/01.exp)

After you have manually tested your solution, you can autotest it by running ./autotest. This will run some basic tests on your program, as well as check for memory leaks/errors.

It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note that you will need to check the output yourself.