BST Operations: Playground (Part 4)

Before we begin

Make sure to copy the previously implemented functions (getSuccessor, getPredecessor, rangeCount, rangeSearch) from the previous playground. The goal is to build a complete implementation across the playground lessons. Having all the functions together will also help you test them together and find any potential wrong interactions.

Implementing the operations

You will implement the pseudocode from the previous lesson in this playground lesson.

Note: At the end of this lesson, you will have a full header for a generic BST, which you can use in any future project!

We will first briefly go over the functions that you need to implement. Then, you can start implementing them in the code widget below.

removeNode

Implement the removeNode function. It should accept a binary search tree and a reference value. The function must remove the node whose value is equal to the reference value if such a node exists. Otherwise, the tree should remain unchanged.

To get more practice, try to implement this function using the reference argument and the return value techniques for updating the tree’s root.

inOrder, preOrder, postOrder

Implement the preOrder, inOrder, and postOrder functions. They should accept a tree and display its nodes in the appropriate order (pre, in, or post). Recall that inOrder is essentially the treeSort function for sorting in ascending order.

Code playground

Perform the implementation inside generic_bst.h (see the comments).

Test your implementation by writing code in the main function from main.c.

You may want to use helper functions. For example, accept a helper function that tells how to compare the values of a concrete type. Recall that not all data types can be directly compared with regular arithmetic operators such as == or <.

Build a few trees of various data types to ensure your functions behave correctly when tested together. Display the trees using printBST with an appropriate helper function.