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?
How would (did) you represent a binary tree node in Java?
How would you represent a binary tree node in C?
In Java, what code is responsible for constructing new instances of binary tree nodes?
How would you do that in C?
Write a function that prints a tree node to standard output (similar to a toString method in Java).
Using what you have so far, write a complete program that constructs and prints several tree nodes.
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?
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.
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.
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.
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?

Add functions Tree_add and Tree_print that connect trees (pointers to Trees) to tree nodes (pointers to Nodes).
Adjust main to use a Tree rather than a Node.
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.
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.
One more extra credit topic: use typedef to get rid of all the explicit pointers in the program.
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?

What is the minimum cost for adding a node using Node_add?

What is the worst-case cost for adding a node?
Under what circumstances would you see that worst-case performance?
What assumption do you need to make about the values being added in order to prevent this wost case behavior?
Should we be concerned?
Back to Tutorial Home