Binary Search Tree.

Doubts never end. If one doubt is removed, another takes its place. It is like removing the leaves of a tree one by one. Even if all the leaves are clipped off, new ones grow. The tree itself must be uprooted. Ramana Maharshi

A Binary Search Tree(BST) is a data structure in which each node can have a maximum of two children. In a BST, for each node, n, the child to the left, n.left is less than or equal to n and the child to the right, n.right is greater than or equal to n. That is, if data y, is stored in n, y is greater than all values stored in the nodes in the left subtree and less than values in nodes in the right subtree. The topmost node is called the root and the nodes without children are called leaf nodes. On average the runtime complexity for BST operation is O(n), where n is the longest path through the tree or the height of the tree. Let’s take a look at how the different BST operations work.

Inserting into a BST has the worst-case scenario runtime of O(n), where n is the height of the tree. The best-case scenario O(log(n)) can be found when you are inserting into a Perfect Binary Tree. This is because if a tree with n nodes is kept balanced, it’s height is log(n), which leads to a lookup operation of O(log(n)). The Perfect Binary Tree has 2^(n+1) — 1 number of nodes, that is, if the height of the tree is 2, then it has 7 nodes. See the image below.

A Perfect Binary Tree with n = 2.

To insert an element into BST, start by examining the root. if the element is less than the root, insert it into the left subtree. If the element is greater than the root, then insert it into the right subtree. See the image below.

Insert element less than the value in the root.

Insert element greater than the value in the root.

Let’s find an item in the BST. The ordered state of the BST allows for efficient navigation of the tree to search for an element. The time complexity is O(n) for the worst-case in a search operation, and every recursive call descends one level in the tree until it goes from the root to the leaf.

To find an element in the BST, we arrive at a given node and compare the element to the data stored in that node. If it is equal, we have found the location. If not, we check if it is greater or less than, if greater, the element can be found on the right subtree. If less than, the element can be found on the left subtree.

Searching for a value less than the root value.

The time complexity of the delete operation is O(n). There are various ways to delete from the BST and it depends on what you want to remove.

To remove the minimum value in the tree, go through the leftmost subtrees until you find the node. To find the maximum, go to the rightmost subtree and delete it.

If the node to be deleted has one child, delete the node and replace it with the child. If the node has two child nodes, simply, use T. Hibbard’s method of deleting the node by replacing it with the successor. This is the more complex case and it might be helpful to list the process in steps:

Step 1: Point to the node to be deleted, call the pointer D.

Step 2: Point to the minimum element from the right tree (the right tree from the element we need to delete), call the pointer R.

Step 3: Move R to the position of D and delete D.

Deleting a node with 2 child nodes.

The node has been deleted.

I hope that this introduction to Binary Search Tree was useful and has at least given you an understanding of its different operations. Please leave questions and feedback in the comment section below. See you in my next blog post.