BST Operations: Playground (Part 3)

Before we begin

Make sure to copy the previously implemented functions (getMin, getMax, getSize, and getHeight) 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 getSuccessor and getPredecessor functions

Implement the getSuccessor and getPredecessor functions. They should accept a binary search tree and a reference value.

• getSuccessor should return the node with the closest but bigger value than the reference value. There should be no other node with a value bigger than the reference but lower than the returned value (no other value between the reference and the returned value).
• getPredecessor should return the node with the closest but smaller value than the reference value. There should be no other node with a value bigger than the return value but lower than the reference (no other value between the returned value and the reference).

The rangeCount and rangeSearch functions

Implement the rangeCount and rangeSearch functions. They should accept a binary search tree and a lower and an upper bound.

• rangeCount should return the number of values from the tree that are between the lower and upper bounds (inclusive).
• rangeSearch should return a dynamically allocated array containing the nodes (or the values directly) that contain values between the lower and upper bounds (inclusive).
  • If you opt to return values instead of nodes, be careful how you copy them inside the array. Not all data types can be copied safely using =, which performs a shallow copy. You may want to use a genericity function that specifies how to copy the value inside the array.
  • Make sure to return the number of nodes added inside the array. Perhaps you can use a reference parameter for this purpose.
  • Think about the worst-case number of nodes inside the range, to know what size to use for the array.

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 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.