C for Java Programmers: Binary Search Tree

George Ferguson

Summer 2018
(Updated Summer 2020)

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License
Creative Commons License

In this lesson, you will create a binary search tree in C. This is a tree data structure with the property that the left subtree of any node contains only values less than the parent and the right subtree contains only values greater than the parent. You should already be familiar with implementing trees using Java.

You should also be familar with the “object-oriented” idioms described in the “Employee” lesson. They will be used but not re-explained in this this lesson. And that lesson expected you to be familiar with the companion C for Java Programmers document.

Each step of the lesson asks you to answer a question or write some code. Do the steps yourself before checking your work by revealing the answer.

Let’s assume that we will store integers in our binary search tree. You could also redo this lesson storing strings or other “comparable” elements.

Start with the design of your data structure. What is stored at each node in a tree that is storing a collection of integers?
Each node in a tree holds an element from the collection (an integer in this case) and references to its child nodes. For a binary tree, each node may have at most two children.
How would (did) you represent a binary tree node in Java?
A class something like the following: class Node { int value; Node leftChild; Node rightChild; } Note that this is a recursively-defined class—a Node contains references to other Nodes.
How would you represent a binary tree node in C?
As you should know from the Objects Lesson, in C you use a struct to define a “structured type” (a type composed of other types): struct Node { int value; struct Node* leftChild; struct Node* rightChild; };

As in Java, this is recursively defined. Kernighan & Ritchie call this a “self-referential structure” (The C Programming Language, 2nd Ed., p. 139–143).

In Java, what code is responsible for constructing new instances of binary tree nodes?
The constructor in your Node class: public Node(int value) { this.value = value; } You create a new instance by calling the constructor: Node n = new Node(123);
How would you do that in C?
We define a “constructor” function that allocates space for an instance of the struct Node type, initializes it, and returns the pointer to it: struct Node* new_Node(int value) { struct Node* this = (struct Node*)malloc(sizeof(struct Node)); if (this == NULL) { return NULL; // Out of memory... } this->value = value; this->leftChild = NULL; this->rightChild = NULL; return this; }

Then just like Java, you create a new instance by calling the “constructor”: struct Node* n = new_Node(123); These idioms were described in the “Employee” lesson.

Write a function that prints a tree node to standard output (similar to a toString method in Java).
void Node_print(struct Node* this) { printf("Node[%d]", this->value); } Note the name of the function and the way the reference to the instance is passed as first parameter. These idioms were also described in the “Employee” lesson.

Using what you have so far, write a complete program that constructs and prints several tree nodes.
Just add a main function to what we have already. Something like: int main(int argc, char* argv[]) { struct Node* node1 = new_Node(1); Node_print(node1); struct Node* node2 = new_Node(22); Node_print(node2); struct Node* node3 = new_Node(333); Node_print(node3); } When you run this program, the nodes will all print one after each other on the same line with no spacing or newlines. You could add calls to printf in between if you wanted.

Download full program: tree1.c

Time to turn nodes into trees. In fact, as you should already know, each node is a tree, or rather, it's the root of a tree. Based on this observation, how would you represent an empty tree?
An empty tree has no nodes. So you need a value of type “pointer to node” that in fact doesn’t point to a node. There’s only one such value in C: struct Node* root = NULL; We can use the reserved word NULL for this, just like null in Java (None in Python, nil in Lisp and Swift, but I digress). You should be comfortable with null references in Java. They’re the same in C except that the keyword is in uppercase.
Using this convention, that an empty tree is a NULL pointer, write a function to add a new integer to a tree maintaining the binary search tree property. Hint: You will need to handle four cases.
The four cases are:
  1. The tree is empty, so the new element will be at the root of the tree.
  2. The element is already in the tree, so there’s nothing to do.
  3. The element is not already in the tree, meaning it belongs in either the left or the right subtree of the tree, depending on its value.
Here's the function: struct Node* Node_add(struct Node* this, int value) { if (this == NULL) { this = new_Node(value); } else if (value < this->value) { this->leftChild = Node_add(this->leftChild, value); } else if (value > this->value) { this->rightChild = Node_add(this->rightChild, value); } else { // Already in tree } return this; }

Note that this function always returns a tree (a pointer to a Node) containing the given element (and all previously-added elements, of course).

Modify your Node_print function to print the entire tree rooted at the given Node. Don’t forget the definition of what an empty tree is. Hint: This is going to be a special kind of function that you should be used to already in Computer Science.
void Tree_print(struct Node* this) { if (this != NULL) { Tree_print(this->leftChild); printf("%d\n", this->value); Tree_print(this->rightChild); } } This recursive function does an in-order traversal of the tree, which means that it prints in... sorted order. Way cool. You could make it print in parenthesized or indented form also. Try it!
Write a complete program that starts with an empty tree, adds some integers to it, and prints it out to show that it has done the right thing.
Here's a main function, for example: int main(int argc, char* argv[]) { struct Node* root = NULL; root = Node_add(root, 20); root = Node_add(root, 10); root = Node_add(root, 5); root = Node_add(root, 15); root = Node_add(root, 30); root = Node_add(root, 40); root = Node_add(root, 20); Node_print(root); } The final call to Node_add has no effect since the value 20 is already in the tree.

Note that we have to always assign the result of Node_add to our variable root, even though in fact the only time the root changes is when the first element is added to the tree. But remember: it's a recursive function. Every time a new element is added, the root of some subtree is created (and hence returned from some recursive call, namely the last one). However in this example, you could, if you wanted to, only assign to root the first time. Try it! But then if you could also remove elments from the tree... Try that also!

Download full program: tree2.c

Let’s tidy up this representation just a bit. It’s certainly elegant to use pointers to tree nodes to represent trees. It’s how Kernighan and Ritchie do it in The C Programming Language, 2nd Ed. Section 6.5 so it must be right. But a more modern treatment would encapsulate the tree nodes inside an opaque data structure that represents trees independently of how they’re implemented.

In Java, you would define a class Tree with an instance variable representing the Node at the root of the tree. How would you do that in C?

Piece of cake: struct Tree { struct Node* root; }; struct Tree* new_Tree() { struct Tree* this = (struct Tree*)malloc(sizeof(struct Tree)); if (this == NULL) { return NULL; // Out of memory... } this->root = NULL; return this; } Notice that an empty tree still involves a NULL pointer to a tree node. A Tree is initially empty, so its root is NULL.
Add functions Tree_add and Tree_print that connect trees (pointers to Trees) to tree nodes (pointers to Nodes).
Just forward the root of the tree to the tree node function: void Tree_add(struct Tree* this, int value) { this->root = Node_add(this->root, value); } void Tree_print(struct Tree* this) { Node_print(this->root); } Note how Tree_add encapsulates the management of the root of the tree, which we had to do ourselves when trees were just pointers to tree nodes.
Adjust main to use a Tree rather than a Node.
int main(int argc, char* argv[]) { struct Tree* tree = new_Tree(); Tree_add(tree, 20); Tree_add(tree, 10); Tree_add(tree, 5); Tree_add(tree, 15); Tree_add(tree, 30); Tree_add(tree, 40); Tree_add(tree, 20); Tree_print(tree); } Nice!

Download full program: tree3.c

This is really enough to demonstrate how to implement a dynamic data structure like a binary search tree in C. But for completeness, add the lookup function that uses the binary search tree property to test whether a value is in the tree. Demonstrate its use in a program.
int Node_lookup(struct Node* this, int value) { if (this == NULL) { return 0; } else if (value < this->value) { return Tree_lookup(this->leftChild, value); } else if (value > this->value) { return Tree_lookup(this->rightChild, value); } else { return 1; // value == this->value } } int Tree_lookup(struct Tree* this, int value) { return Node_lookup(this->root, value); } An elegant recursive function. Trees are so cool. Note the use of 0 for false and non-zero (in this case 1) for true. Here's a main function to test it: int main(int argc, char* argv[]) { struct Node* root = NULL; root = Tree_add(root, 20); root = Tree_add(root, 10); root = Tree_add(root, 5); root = Tree_add(root, 15); root = Tree_add(root, 30); root = Tree_add(root, 40); root = Tree_add(root, 20); Tree_print(root); printf("%d\n", Tree_lookup(root, 15)); // 1 printf("%d\n", Tree_lookup(root, 99)); // 0 } You could also use the result of Tree_lookup in a conditional statement or loop. Try it!

Download full program: tree4.c

For extra credit: write a function that takes as arguments a tree and a pointer to a void function that itself takes a single int as its arguments. (See the C for Java Programmers document if you need a reminder about function pointers.) Your function should call the given “callback” function with each value in the tree, one after the other in sorted order.
I won't give you the full answer, but I will give you the signature of the function: void Node_walk(struct Node* this, void (*callback)(int)) And by the way you’ve already written a function very similar to this one...

You will also need a function Tree_walk that forwards to Node_walk on its root.

And then here's an example of a callback function that just prints the given value: void myCallback(int value) { printf("%d\n", value); } If you need a refresher on passing function pointers as arguments to other functions, check out Section 8.8 of the C for Java Programmers document.

With this callback function, what will a call to Tree_walk do? Think about it... It will print the elements in the tree in sorted order. Way cool.

One more extra credit topic: use typedef to get rid of all the explicit pointers in the program.
Add the following statements before their respective structure definitions: typedef struct Node* Node; typedef struct Tree* Tree; Now “Node” is the type “pointer to Node structure” and “Tree” is the type “pointer to Tree structure”. If that sounds confusing, remember that the name following the keyword struct in a structure definition is not a type but rather what C calls a “tag.”

Now replace all occurences of struct Node* with simply Node and similarly for Tree. The result looks pretty much like Java, except for your “new_” functions (which are pure boilerplate), the lack of namespaces for “method” (function) names, and the need to pass the “instance” as the first argument to every “method.” Still, pretty cool!

Download full program: tree6.c

Hey! Before you leave this lesson, how about a bit of Computer Science to go with the C programming?

How would you evaluate the cost of adding an element to a binary search tree like this one?

Clearly the cost of adding an element to a binary search tree like this is the number of times that Node_add calls itself recursively (since the other cases take constant time).

What is the minimum cost for adding a node using Node_add?
The minimum cost is one call, which happens if the tree is empty (NULL) or the value is already stored at the root of the tree.

What is the worst-case cost for adding a node?
Every new node added to the tree is a leaf. The cost of adding a new child to an existing leaf is the length of the path from the root to that leaf, since each recursive call to Node_add moves from a node to one of its children.

As implemented, nothing guarantees that our tree is balanced in any way. The worst case is that all the nodes (except the last) have exactly one child, meaning that they form a chain of nodes from the root to the only leaf. In that case, the cost to add a new element is linear in the size of the collection.

Under what circumstances would you see that worst-case performance?
If the elements are added in increasing (sorted) order, then each new node will always be the new right child of the rightmost existing node. The nodes will form a single chain of right children from the root. If the elements are added in reverse (decreasing) order, the chain will form to the left.

There are other orderings that create chains that mix left and right children, although still with only one child per node (except the last). In fact, there are 2n such orderings over n elements.

What assumption do you need to make about the values being added in order to prevent this wost case behavior?
The ideal situation is that the elements arrive in an order that creates the shallowest tree. This will be a complete binary tree (other than the deepest level, which may not be full). In that case, the worst-case cost to add or lookup is the log2 of the number of elements in the collection.

It’s not really enough to say simply that the order must be random. Assuming that “random” means that all sequences are equally likely, then the probability of the worst-case occurring is 2n / n! since there are n! total orderings of n elements. This drops below 1% for n=8 and gets small very quickly after that. But under what circumstances can you be confident that all sequences are equally likely (see next question)?

Should we be concerned?
Yes we should be concerned. It would not be uncommon for values to be added to the collection in sorted order. For example, they could have come from a database query that sorted its results. Or they could be sequential values of a linear functional relationship. Or they could have been produced by iterating over (walking) a binary search tree! In any event, it would be downright annoying if, having gone to the trouble of sorting the elements in the first place, we ended up with worse performance after putting them into a data structure whose entire purpose is to maintain a sorted order efficiently! This suggests that a balanced-tree implementation might be a better choice for large datasets.

That’s why we do Computer Science.

Back to Tutorial Home