Practice Exercise
Smallest Value in a BST
Your task is to write a function, bstGetSmallest, that returns a pointer to the node containing the smallest value in the given BST. If the tree is empty, return NULL.
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/bstGetSmallest/downloads/bstGetSmallest.zip
If you're working at home, download bstGetSmallest.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 |
| testBstGetSmallest.c | Contains the main function, which reads in a BST from standard input, calls bstGetSmallest and prints out the result |
| bstGetSmallest.c | Contains bstGetSmallest, 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
./testBstGetSmallest
Enter the preorder traversal of the BST: 6 5 2 8 9
BST:
6
/ \
5 8
/ \
2 9
bstGetSmallest returned: 2
./testBstGetSmallest Enter the preorder traversal of the BST: 5 8 6 9 BST: 5 \ 8 / \ 6 9 bstGetSmallest returned: 5
./testBstGetSmallest Enter the preorder traversal of the BST: BST: X bstGetSmallest returned: NULL
Testing
You can compile and test your function using the following commands:
make # compiles the program ./testBstGetSmallest # tests with manual input, outputs to terminal ./testBstGetSmallest < input-file # tests with input from a file, outputs to terminal ./testBstGetSmallest < 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.