Practice Exercise
Deleting the Largest Value in a BST
Your task is to write a function, bstDeleteLargest
, that takes a BST and a pointer to an integer max
, and deletes the largest value in the given BST, sets *max
to the value that was deleted, and returns the root of the updated tree,
Assumptions and Constraints
- The given BST is non-empty.
- You must not use arrays.
- You must not use any variant of
malloc
, either directly or indirectly. - You must not change the values in any nodes.
Download
While in your practice exercises directory, run the following command:
unzip /web/cs2521/practice-exercises/trees/bstDeleteLargest/downloads/bstDeleteLargest.zip
If you're working at home, download bstDeleteLargest.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 |
testBstDeleteLargest.c | Contains the main function, which reads in a BST from standard input, calls bstDeleteLargest and prints out the result |
bstDeleteLargest.c | Contains bstDeleteLargest , 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
./testBstDeleteLargest Enter the preorder traversal of the BST: 5 3 2 7 8 BST: 5 / \ 3 7 / \ 2 8 BST after deleting largest: 5 / \ 3 7 / 2 The largest value was 8
./testBstDeleteLargest Enter the preorder traversal of the BST: 6 2 1 4 BST: 6 / 2 / \ 1 4 BST after deleting largest: 2 / \ 1 4 The largest value was 6
./testBstDeleteLargest Enter the preorder traversal of the BST: 2 3 7 5 BST: 2 \ 3 \ 7 / 5 BST after deleting largest: 2 \ 3 \ 5 The largest value was 7
Testing
You can compile and test your function using the following commands:
make # compiles the program ./testBstDeleteLargest # tests with manual input, outputs to terminal ./testBstDeleteLargest < input-file # tests with input from a file, outputs to terminal ./testBstDeleteLargest < 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.