Data Structures: Binary Search Trees

In my last article, I explained Stacks and Queues. For this issue, I will now dive into more complex data-structures, but before I define what a Binary Search Tree is. Let us define what a simple Tree is in the world of computer science.

Tree: A data structure that consists of nodes in a parent-child relationship.

On the left, is a visual representation of a simple Tree. You can think of Trees in terms of an actual tree, but it is upside down.

There are a couple of terminologies you have to be familiar with when dealing with these types of data structures

Root: The top node in a tree, in the case of the example, it is 2.

Child: A node directly connected to another node when moving away from the root. As you can see from the example, 7 is a child of 2.

Parent: The converse of a child, in the case of the example, 2 is the parent of 7.

Siblings: A group of nodes with the same parent. So in this case, 2, 10 and 6 are said to be siblings.

Leaf: A node with no children. For the case of the example, 5, 11 and 4 are said to be leaves of the tree.

Edge: The connection between one node and the other.

Trees have many applications and we hardly notice it. Examples include the HTML DOM Tree, folders within whatever Operating System you are currently using and also the Abstract Syntax Tree, which is just a way of representing the syntax of a programming language in a “tree-like” structure. This tree represents all of the constructs of the language and its subsequent rules

Binary Search Trees

A Binary Search Tree (BST) is a special variant of Trees. They have special rules that make them unique. These are listed below.

1) Every node within the tree must have at most 2 children.
2) Every node to the left of the parent node is always less than the parent node.
3) Every node to the right of the parent node is always greater than the parent node,

As you can see from the example on the left, on the left side of the root of the tree (50), every value is less than the root, and on the right side, every value is greater than the root. The rules are followed even as you traverse down through the BST, as you can see on the left side of 30, the value is 20, which is obviously less than 30 and on the right side of 30, the value is 40.

You can implement a BST using the linked-list implementation, similar to how I implemented Stacks and Queues on the last issue.

A node within a BST as 3 properties, right, left and value. Right and left are really just pointers that do what they say they do. They point the current node to the nodes on the left and right sides. The value is just the data the node holds. Which can be a string, integer, etc but for the sake of simplicity, we are going to visualise with only integers.

There are two important methods within a BST, that is insert() and find(). Insert allows you to insert a node within a BST by checking if the node to be inserted is greater or less than the root node. We use this strategy as we traverse down the tree in order to insert it to the correct place. The screenshot of the code above with pseudocode explains the algorithm on how we traverse down the BST in order to insert the node in the correct place.

The find() method is similar to the insert() method with one crucial difference, we are not inserting a new node within the tree but finding an already existing node and returning it. Both methods within the BST are essentially looping (traversing) through the BST until a condition has been met and we return what we want.

Time Complexity

The best case for both the insert and the find method is O(log n). This is because of the arrangement of data within the BST.

Let's bring back the previous example. If we were to insert the number 10 within this tree, we can completely disregard the right-hand side of the tree, the algorithm will know to only utilise the left side of the tree in order to insert the node. Due to this, if we were to increase the size of this BST by adding children to the leaves and do the same operation, we would really be increasing the number of steps to traverse from the parent to the child by only 1. This explanation is the same for the find() method.