Goals

To implement a binary search tree.

Setup

Mount the COURSES drive and remember to save everything into STUWORK. If you don’t do this, everything you write will disappear when you log out!!!!

  • Create a new folder in your STUWORK called BSTLab
  • Download the starter code and put it into your lab folder
  • Open your BSTLab folder in VSCode

Exercise 1

Look at the code in main and draw out what the binary search tree will look like after all the insertion steps.

Exercise 2

Start with implementing insertKey. Remember to save the values from the recursive calls and set them to the appropriate variables! Try out running your code and make sure that you get a correct in order traversal.

Exercise 3

No implement minValue, a helper function that you’ll want. Remember to test your code by adding a call to minValue in main.

Exercise 4

Finally implement deleteRec and make sure that everything works.

Upload your completed lab to Moodle for an extra engagement credit.

Extra

Binary search trees can easily become imbalanced and lose all their benefits. How could you detect that your tree was becoming imbalanced and fix it?