WTF is a Binary Search Tree?

The binary tree is a type of data structure that is commonly used to represent hierarchical data. It is an efficient way of storing and organizing data that is ranked in parent nodes and child nodes.

Essentially, the binary tree is a collection of data, called nodes, linked together in order to simulate a hierarchy, making it a non-linear data structure as compared to linear data structures such as a linked list, or an array.

A binary search tree is a unique structure because no parent node can have more than two child nodes, as well as searching through a tree is simple since all of the nodes in the right subtree will be greater than the root and all of the nodes in the left subtree will be less than the root.

For example, in the image above, we can conclude that this is a binary search tree because since 3 is less than 8, it goes into the left subtree and since 10 is greater than 8, it will go into the right subtree. Furthermore, we can assume that no node can ever cross over subtrees, ensuring that all of the nodes less than the root will always be on the left subtree and vise versa. Keep in mind that changing a node’s value that will make it either less or greater than the node will obstruct the tree. If the value of the right child node of 3, which is 6, were to be changed to 9, this would no longer be a binary tree, as although 9 is greater than 3 and is on the right side of 3, 9 is also greater than the root 8, so it can’t remain on the left.

Within a binary search tree, the following operations can be performed: in a tree, we want to be able to search for a single node, insert a node, and remove a node. The key to performing any of these behaviors is the height of the binary tree, which is determined by the number of nodes from top to bottom.

There are three different types of binary trees. A binary tree is full if all nodes have two children, except the leaves, which will have zero children. A binary tree is complete if all the hierarchical levels are filled up with nodes, with the exception that the lowest level will have zero children and the level before the last will have either 0, 1, or 2 child nodes. A binary tree is perfect if all nodes have two children and all leaves end on the same level. To check whether a binary tree is balanced or not, the difference between the height of the left and right subtree is not greater than 1.

To perform a search operation in a binary tree, we will use a binary search. A binary search first finds the middle point of a predefined search space. Then, it checks whether the target number is less or greater than the midpoint, moving left is less or right if greater, concurrently cutting the search space in half. This causes the time complexity of the binary search to always be O(log n).

Let’s take a look at this example to perform a binary search of an unbalanced binary tree.

Here is a sample of what the binary tree search operation code might look like:

def _find_node_iterative(self, item):
        node = self.root
        # Loop until we descend past the closest leaf node
        while node is not None:
            if item == node.data:
                return node
            elif item < node.data:
                node = node.left
            elif item > node.data:
                node = node.right
        # Not found
        return None

In the following example, we will search for the node with a value of 64. Since we know 64 is greater than the root, 60, we will be looking at the right subtree whilst comparing the child node to the target value until it is found. Our current search space becomes n/2. Moving on, we continue going down the tree onto the node with value 74. Since our target is less and the parent only has one child, we continue. Our updated search space: n/4. Next, 64 is less than 65 we look to the left. Search space: n/8. Finally, we see that 64 is greater than its’ parents node of 63, we look to the right and find out node. Our final search space becomes n/16 since it took 4 binary searches to find our target node.

Now let’s take a look at inserting a node into a binary search tree.

In the following example, we will insert the node with a value of 18. Starting from the root, 18 is greater than 10, therefore we will be inserting it on the right subtree. Moving forward, we see that 18 is less than 19, so we go to the left child. Since 18 is greater than 17, but there is no child node, we create (insert) a new node and the process is complete. Our new binary tree will look like this.

Here is a sample of what the binary search tree insertion code might look like:

def insert(self, item):
        if self.is_empty():
            self.root = BinaryTreeNode(item)
            self.size += 1
            return
        parent = self._find_parent_node_recursive(item, self.root)
        if parent == None:
            self.root.left = BinaryTreeNode(item)
        elif parent.data > item:
            parent.left = BinaryTreeNode(item)
        elif parent.data < item:
            parent.right = BinaryTreeNode(item)
        self.size += 1

If you have read this far, you now have a basic understanding of how search, insertion, and deletion work for a binary tree. Please feel free to leave a review in the comments below.

(p.s. I am aware that the node I inserted, 19, is already on the binary tree 😂 I posted the article already before I realized. Although it still augments the article nevertheless. Thank you for understanding)