In this article, we will be going to discuss the Binary Search Tree data structure.

Pre-req: Binary Tree, Tree Traversals

What is a Binary Search Tree?

A Binary Search Tree is a Binary Tree with two additional properties:

• Nodes to the left of the root are lesser than the root node and the nodes to the right of the root node are greater than the root node. i.e
  left Node Values < root Node Value < Right Node Values
• The above property is followed down the tree recursively.

Now, we will understand these two properties in-depth with the help of an example.

Example:

This is a Binary Tree.

We will check for the properties of the binary search tree, one by one:

Property 1: Nodes to the left of the root are lesser than the root node and the node to the right of the root node are greater than the root node.

If we clearly observe the root nodes and the nodes to their left and right, we can see that the first property is satisfied.

Property 2: Property 1 is followed down the tree recursively.

It is important that this property is followed by all the nodes recursively (leaf nodes are exempted as they don’t have any children). As property 1 is satisfied at the root, let us check for other nodes as well.

We can see that for all nodes, property 1 is satisfied, hence property 2 for the entire tree is satisfied.

As both properties are satisfied, we can say that the given binary tree is a binary search tree.

Some Examples of Incorrect Binary Search Trees:

• For the first tree, property 1 is not satisfied as the left node value(10) is greater than the root node(8).
• For the second tree, property 1 is satisfied at the root node, but is not satisfied at the root with value 15, hence property 2 of the entire tree is not satisfied.

Property 3: Handling Duplicates

Binary Search Trees are expected not to have duplicates but in case we want to have duplicate values, two strategies can be used:

• Modifying the relationship

We can modify the relationship that defines a binary search tree and say that duplicate values can appear on the left side of the root node, i.e: the relationship becomes:
left Node Values <= root Node Value < Right Node Values

In the previous example, if we had to accommodate two 8’s, it would be done like this.

• Having a frequency count in node structure.

We can modify the node data structure to contain data as well as a frequency value. This way we can track how many occurrences of a particular value are there.

Why should we use a Binary Search Tree?

In a Binary Search Tree, we can search for any node in O(logN) time where N is the number of nodes. It is because, at every node, we know that we will find the value we are looking for either in the left subtree or in the right subtree, therefore we are reducing the search space by half in every step. This is nothing else, rather than the binary search itself. Note: It is generally assumed that a given binary search tree is a balanced binary search tree. A balanced binary search tree means that the difference between the left height and right height of the tree doesn’t exceed 1. In simpler words, the height of the given tree is near to logN. This assumption is important because the following two trees are also binary search trees but here the cost of the search operation is O(N).

Special thanks to Anshuman Sharma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article