# Searching & Sorting w/ Binary Search Trees

###
Blake Khan
Apr 7
*
Originally published at
blog.blakekhan.com
on
Apr 05, 2019
*
・4 min read

###
**Introduction**

Binary Search Trees are an incredibly useful data structure that holds comparable values in a particular order.

With this particular ordering, it allows for fast lookups and a straightforward way to sort the values in the tree.

Regarding use cases, this data structure is one of the bases for more abstract data structures such as sets and maps.

###
**Definitions**

Before we talk about ordering and searching with Binary Search Trees (BSTs), let’s make sure we’re on the same page regarding terminology.

A **Node** holds

- A value.
- References to other nodes.

A **Tree** is a data structure that has

- One parent node.
- Zero, one, or multiple child nodes.
- No duplicate nodes.
- No node that references the root node (meaning no looping).

A tree is implemented with one root node, consisting of children of subtrees that have the properties above.

- A parent node is considered as the root node of that specific subtree.
- The root node is the starting node for the entire tree.

When you hear the term “Binary Tree”, you might feel a little intimidated! But worry not, it’s a straightforward concept to grasp.

A **Binary Tree** is a tree with

- At most two child nodes (one left, one right).

Now let’s define what this entire post is about - Binary Search Trees.

A **Binary Search Tree** is a particular type of binary tree where

- The left child node is less than the parent node.
- The right child node is greater than the parent node.

###
**Implementation**

I chose to use C as the language for the implementation examples, as the machine you are reading this on likely has a C compiler.

Here’s the code for the Node which I’ll be referencing in following examples below.

```
typedef struct {
int val; // The value the node is holding.
struct Node* left; // Pointer pointing to left child node.
struct Node* right; // Pointer pointing to right child node.
} Node;
```

###
**Sorting**

There are different ways that you can traversal a tree. There is pre-order, in-order, out-order, post-order, etc. As this post is specifically about Binary Search Trees, I’m not going to go into too much detail about generic tree traversals. However, in-order traversal plays a significant role in BSTs.

In-Order traversal follows the pattern `LEFT PARENT RIGHT`

.Let’s take the following BST as an example:

If you traverse the BST using in-order traversal, you’ll start with the left node (3), move back to the parent node (5) and end with the right node (7), resulting in 3, 5, 7.

Take a look at that result, does anything stick out to you? In case you didn’t notice, it returned a sorted result!

Try it with any BST; you will always end up with a sorted result. Not convinced? Let’s try it one more time with a more complex BST.

Remember that in-order traversal goes like this: Left, Parent, Right.

So starting at 50, go left to 27. 27 has a left child (7), so go there next. 7 doesn’t have a left child so that’s our first entry. Then move up back to 7’s parent (27) which is our second entry, then go to 27’s right child (42) which is now our third entry.

So far, our result is:`7, 27, 42`

Now, we’re done with the subtree where 27 is the root. 50 is the parent of 27, so that’s our fourth entry. We then head to 50’s right child, 99. However, 99 has a left child (84), so we go there instead. 84 is now our fifth entry. We then go to 84’s parent (99) which is our sixth entry. Then we go to 99’s right child, which doesn’t exist - so we’re done!

Our result from the in-order traversal is:`7, 27, 42, 50, 84, 99`

Would you look at that, it’s completely sorted!

Here’s a C implementation of in-order traversal:

```
void printInOrder(Node **parent) {
// Safety Check.
if (parent == NULL) {
return;
}
// Print Left Subtree.
if ((*parent)->left != NULL) {
printInOrder((Node **) &((*parent)->left));
}
// Print Parent.
printf("%d, " , (*parent)->val);
// Print Right Subtree.
if ((*parent)->right != NULL) {
printInOrder((Node **) &((*parent)->right));
}
}
```

###
**Searching**

The average efficiency of searching for a value in a BST is `O(log n)`

. This means that on average, only half of the nodes in the BST needs to be searched. The worst case is `O(n)`

where all nodes need to be searched.

Searching takes advantage of three features of BSTs:

- There are no duplicates.
- Values can be compared to each other.
- Values to the left are smaller than the parent, and values to the right are greater than the parent.

Not only is this data structure favored for its search efficiency, it’s also preferred for its ease of implementation. The search function can be implemented recursively.

Here’s a `contains`

function implemented in C:

```
bool contains(Node **parent, const int *value) {
// Safety Check.
if (parent == NULL) {
return false;
}
// Found!
if ((*parent)->val == *value) {
return true;
}
// Check left subtree.
if (*value < (*parent)->val) {
if ((*parent)->left == NULL) {
return false;
}
return contains((Node **) &((*parent)->left), value);
}
// Check right subtree.
if ((*parent)->right == NULL) {
return false;
}
return contains((Node **) &((*parent)->right), value);
}
```

As you can see in the implementation, we disregard the right subtree if the value we are looking for is less than that subtree's parent value. Likewise, we disregard the left subtree if the value we are searching for is greater than the subtree's parent value.

###
**Full Demo**

If you’d like to try out or view the full C implementation demo that includes some testing, here you go!

###
**Wrapping things Up**

Binary Search Trees are wonderful data structures when it comes to searching and sorting. By taking advantage of in-order traversal and the properties of this special tree, you can implement both searching and sorting functions not only efficiently, but also easily.

Thanks for reading!