BST Operations: Playground (Part 3)
Implement generic BST algorithms in the C language.
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.
- 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
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.
Get hands-on with 1200+ tech skills courses.