BST Operations: Playground (Part 1)

Implementing the operations

Welcome to the first playground lesson where you’ll implement the pseudocode from the previous 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.

Helper functions

Before implementing any algorithms, you should implement two helper functions.

• allocNode will allocate a new node inside the generic tree.
  • We suggest accepting a value void* that you’ll use to initialize the value field inside the node. The expectation is that the caller of allocNode will provide freshly dynamically allocated memory, and allocNode can take ownership of it. We guarantee this is the case inside the project during the automatic testing.
  • The left and right fields should point to empty trees. In other words, allocNode should allocate a tree consisting of only one node.
• freeBst to fully deallocate a binary search tree and its values. You may need to use a generic helper function to free the value. Since the implementation is generic, different data types may need to be freed differently.

The findNode function

Implement the findNode function. It should accept a binary search tree and a value.

• If the tree contains a node with the given value, return that node.
• If the tree doesn’t contain the given value, return the insertion point of that value inside the tree.
• Return NULL if the tree is empty.

The contains function

Implement the contains function. It should accept a binary search tree and a value. Return 1 if the tree contains a node with the given value. Otherwise, return 0.

You may want to use the findNode function for implementing contains.

The insertNode function

Implement the insertNot function. It should accept a binary search tree and a value. The function should insert the value inside the tree at the appropriate location, according to the BST ordering property. Don’t perform the insertion if the tree already contains the value. Return 1 upon a successful insertion and 0 otherwise.

You may want to use the findNode function for implementing insertNode.

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.

You may want to use helper functions. For example, accept a helper function that tells you 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.