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

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.

Follow up: Can you solve this using both iterative and recursive approaches?