Pseudocode Lessons

Introduction

In this lesson, we’ll understand the structure and purpose behind the playground lessons, where you’ll implement the algorithms described in the first pseudocode lesson.

Here’s what we mean by playground lesson:

• You have complete control of how you design the data structure and how you implement the functions.
  • You decide which arguments the functions will accept.
  • You decide the return values.
  • You can even change the name of the functions if you prefer.
  • You choose which strategy to use to implement the functions. You can use reference pointers, the return strategy, or something completely different.
  • The only restriction is that your implementation must be generic. The BST implementation must work out of the box for any data type, be it an already existing data type (int, float, char*) or a user-defined data type (struct).
• We don’t check the playground lessons automatically.
  • It is your responsibility to test your implementation on various data types, find potential bugs or issues, and fix them. In the real world, no one will provide you with test cases.
  • You’ll get in the habit of considering all these edge cases while writing code.
  • We do it like this because thinking about edge cases, trying to find inputs, and where the code may fail will help you truly understand the data structure, your implementation, and its weak and strong points. In short, this is a valuable skill that we want to teach you.

At the end of this chapter, after all the playground lessons, you’ll have a generic binary search tree header, which you can use any time you need this data structure (for example, inside the project).

Note: Since the project is graded automatically and it uses your generic BST implementation, it will catch any remaining bugs (if they exist) in your generic BST implementation. However, please test thoroughly. Your goal should be to detect as many issues as possible during the data structure development phase.

Solutions

We provide complete solutions for the tasks inside the playground lessons inside the Appendix chapter. Please note that we strongly suggest you don’t check the solution until you give it a fair try. Please resist the urge to look at the solution after encountering the first bump in the road.

Yes, it will be harder, but you’ll learn much more by putting in the effort (writing code, finding test cases, and fixing bugs) than you would by simply looking over the solution.

We put the solution inside the Appendix so they are “out of the way” to further reinforce the idea that you shouldn’t go there unless needed.

Playground structure

Below are details about the structure of the code playgrounds.

Files structure

There are two files in the code widget:

• main.c: It contains the main function, from where you should call the functions you’ll write, create trees and check that they work correctly on those trees. We encourage you to test on multiple data types, not only integers. Testing on two or three different data types should be enough.
• generic_bst.h: You’ll build your BST implementation inside this file. By default, we only provide a buildExampleTree which creates a binary search tree containing the nodes 1, 2, and 3. Note it does not check against NULL, as it’s simply an example function for early testing.

To print the generic BST in a pleasant format, we use a header file from the internet, which will allow us to visualize the trees nicely. Sadly, the source is no longer available, and a wayback machine is the only way of visualizing the code.

Note: We don’t show the print_tree.h file inside the code widget to reduce clutter, but it’s imported automatically.

In short, write your implementation in generic_bst.h and test by calling the implementation inside main.c. Use the functions from print_tree.h to display the trees in a readable format. Test on various data types by creating the helper functions needed to make your generic BST implementation work on the data types.

Data structure definition

The BST structure looks like so:

typedef struct SGenericBst
{
	void* value;
	struct SGenericBst* left;
	struct SGenericBst* right;
}TGenericBst;

It contains a value pointer and pointers for the left and right children. The BST is generic, so we use void*. Please don’t change this structure definition.

Printing trees

To display a BST in an easily readable way, use the function printBST from the print_tree.h file. It accepts a TGenericBst pointer for the tree’s root and a format function. This format function is a genericity helper function, which ensures that the print function works for any data type. The type of format function is as follows:

typedef void(*TSPrintFunc)(char*, void*);

It should fill the data pointed to by the void* in the buffer pointed to by the char*.

For an example of how to write such a function, see the provided sprintInt example. The format function should cast the value pointer to its correct type and pass it to sprintf. The buffer is an internal structure of the binary tree printing algorithm. Please don’t alter it in any way besides calling sprintf on it.

Below is the starter code. Run it and observe how the widget displays the example tree. You don’t need to do anything else here.

Inside it, we call the buildExampleTree function from generic_bst.h, which builds a generic BST of integers.

We then display the tree using printBST, which takes the tree and a formatting function (sprintInt) as arguments. The formatting function is described above.