BST Operations: Playground (Part 2)

Before we begin

Make sure to copy the previously implemented functions (allocNode, freeBst, findNode, contains, and insertNode) 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’ll implement the pseudocode from the previous lesson in this playground lesson.

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

The getMin and getMax1 functions

Implement the getMin and getMax functions. They should accept a binary search tree and return the nodes containing the minimum (getMin) and maximum (getMax) values inside the tree. You may decide to return NULL if the tree is empty or not handle this case. If you pick the second option, it will be the caller’s job to ensure that the tree contains at least one element before calling getMin and getMax. Since you’ll call these functions in the second part of the project, the design is up to you.

The getSize and getHeight functions

Implement the getSize and getHeight functions. They should accept a binary search tree.

• getSize should return the number of nodes inside the tree.
• getHeight should return the height of the tree. The tree’s height is the length (number of nodes) of the longest path inside the tree from the root to a leaf node.

Coding playground

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

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

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.