Implementation Tips and Tricks

Introduction

The course’s goal is to learn how to write pointer-intensive code. Therefore, after understanding binary search trees at a conceptual level, you’ll have to implement the functions in C using pointers and memory allocations. After that, inside the project, you’ll use the newly implemented structure to solve some common real-life problems.

The lessons in this chapter will be in pairs:

• A pseudocode lesson where we understand the ideas behind the algorithms for binary search trees.
• A playground lesson where you will implement the algorithms in C. Make sure to understand the logic behind the algorithms. Otherwise, it will be hard to implement them in C.

The purpose of this lesson is to give some tips and tricks for implementing the functions in C using pointers. Binary search trees are recursive, so writing recursive code is the easiest way of implementing this data structure.

The question that arises is how to blend pointers with recursion. At some point, we will need to change some of the pointers that the recursive functions receive as an argument. You need to know some general techniques for doing this. The problem is similar to the problem of changing the head node of a linked list using a reference pointer.

Note: We won’t show these tips on binary search trees, as implementing them for a BST structure is your job. We’ll show generic examples that present the techniques.

Assume we have a function called operation. Its job is to perform some operation. The function needs to change the pointer received as an argument to do its job.

void operation(int* ptr)
{
    //how can the function operation change the memory location where ptr points to?
    //doing ptr = address doesn’t work, as it will change a copy of ptr, and the change won’t be visible to the caller	
}

In the examples below, we’ll ignore the memory deallocation part, as it isn’t the focus of the lesson.

Using a reference pointer

The first solution is to pass the pointer by reference, which will allow the function to change where the pointers point to. Recall that this solution uses pass by reference instead of pass by value.

The operation function will accept a pointer to our pointer. A pointer to int* is int**. Notice that after calling operation, ptr points to a different location. The change is visible inside main.

Using *ptr allows us to change where the ptr pointer from main points to. Dereferencing twice allows us to change the value of the memory that the pointer from main points to.