C Binary Search Tree

Summary: this tutorial introduces you to binary search tree data structure and how to implement it in C.

Introduction to binary search tree

C Binary Search Tree

Binary Search Tree

A binary search tree or BST is a binary tree in symmetric order.

A binary search tree can:

  • Be empty
  • Have a key and not more than two other subtrees, which are called left subtree and right subtree.

A binary search tree is in symmetric order, it means:

  • Each node contains a key.
  • Each node’s key is smaller than all node’s keys in the right subtree and bigger than all node’s keys in the left subtree.

A binary search tree is also known as sorted or ordered binary tree.

Binary search tree operations

There are some common operations on the binary search tree:

  • Insert – inserts a new node into the tree
  • Delete – removes an existing node from the tree
  • Traverse – traverse the tree in pre-order, in-order and post-order. For the binary search tree, only in-order traversal makes sense
  • Search – search for a given node’s key in the tree

All binary search tree operations are O(H), where H is the depth of the tree. The minimum height of a binary search tree is H = log2N, where N is the number of the tree’s nodes. Therefore the complexity of a binary search tree operation in the best case is O(logN); and in the worst case, its complexity is O(N).

The worst case happens when the binary search tree is unbalanced. Many algorithms have been invented to keep a binary search tree balanced such as height-balanced tree or AVL trees of Adelson-Velskii and Landis, B-trees, and Splay trees.

C binary search tree implementation

We can use a structure to model the binary search tree node a follows:

The node structure has three members:

  • data: stores node’s key, which is an integer. You can store a string, a pointer to a structure or (void*). For the sake of simplicity, we will use a binary search tree of integers.
  • left: points to the left subtree.
  • right: points to the right subtree.

To create a new node, we use the malloc() function to allocate memory dynamically as follows:

To compare the data of two nodes, we can compare two integers. However to make it more extensible, we can pass a callback to any function that has comparison between two keys of nodes. The callback for comparing two nodes is defined as follows:

Later on you may change the type of data to string, float, or even void*, and change the comparer callback accordingly.

Insert a new node into the binary search tree

If the binary search tree is empty, we just create a new node, otherwise we start from the root node:

We find the proper position for the new node by comparing the new node’s key with the root node’s key. If the key of the new node less than the root node’s key, we go to the left subtree. If the key of the new node is greater than the root node’s key, we go to the right subtree. We do this step recursively until we find the correct position in the tree to insert the new node.

The following illustrates the insert_node function:

Delete a node from the binary search tree

Deleting an existing node in the binary search tree is little more complicated. There are three cases that we should consider:

Case 1. Delete a leaf node i.e., node that has no children. We just need to remove it. The following example illustrates how to remove the leaf node e.g., 13

Binary Search Tree - Remove Leaf Node

C Binary Search Tree – Remove Leaf Node

Case 2. Remove a node that has 1 child node, we replace it with its child node and remove it e.g., to remove node 10 in the following picture.

Binary Search Tree - Remove Node with 1 Child

C Binary Search Tree – Remove Node with 1 Child

Case 3. To remove a node that has two child nodes or two children, we find its in-order successor node, which is the next node in in-order traversal of the tree, and replace it with the in-order success node.

For example, to remove node 3, we find its in-order successor node, which is 4, and replace the node 3 by 4 as illustrated in the following picture.

Binary Search Tree – Remove Node with Two Children

Binary Search Tree – Remove Node with Two Children

The following is the delete node function that uses recursive function in C:

Search for a specific key in the binary search tree

To search for a specific key in the binary search tree, we start from the root node. If the tree is empty, the key does not exist. Otherwise, if the root node’s key is equal to the key, the search is successful, we terminate the search. If the key is less than the root node’s key, we search the left subtree. Likewise, if the key is greater than the root node’s key, we search the right subtree. We repeat this step recursively until the key is found or subtree is NULL.

Traverse the binary search tree

We can traverse the binary search tree once it is created by traversing recursively to the left subtree of the root node, accessing the root node’s data, and then recursively traversing to the right subtree of the root node. This is called in-order traversal of a binary tree.

Because of the rules of the nodes’ keys in the binary search tree, this in-order traversal always creates a sorted list of nodes.

The following is the in-order traversal function of the binary search tree:

Notice that we pass a callback to the traverse function so that we can manipulate the node dynamically. The callback is defined as follows:

Remove all nodes

We must deallocate memory allocated for all the nodes in the binary search tree. We can create a function named dispose() to do this:

C binary search tree program

Before creating a program to test our binary search tree, we need to create some functions for:

Comparing two integers:

Displaying a node:

And a function for displaying the whole tree:

Now it’s time to play with the binary search tree:

The following is the output of the binary search tree program in C:

In this tutorial, you have learned how to implement the binary search tree in C.