C for Java Programmers: Binary Search Tree

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.

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.

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

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);

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.

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.

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

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.

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

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!

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

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.

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.

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

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

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.

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

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

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.

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.

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 2ⁿ such orderings over n elements.

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 log₂ 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 2ⁿ / 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)?

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.