What Is Binary Search Tree in Data Structure With Example?

What Is Binary Search Tree in Data Structure With Example?

A binary search tree (BST) is a type of data structure that is commonly used in computer science and programming. It is a binary tree where each node has at most two children, referred to as the left child and the right child. The BST property ensures that the values in the left subtree of a node are less than or equal to the value of the node, and the values in the right subtree are greater than or equal to the value of the node.

Let’s understand this concept with an example:

Example:

Consider a scenario where we have a list of integers: 5, 3, 8, 1, 4, 7, 10. We want to create a binary search tree using these values.

Step 1: Creating the Root Node

The root node is created by selecting an arbitrary value from the list. In this case, let’s choose 5 as our root node.

Step 2: Inserting Nodes

To insert nodes into our binary search tree, we compare each new value with the existing nodes and follow these rules:

• If the new value is less than the current node’s value, we move to its left child.
• If the new value is greater than or equal to the current node’s value, we move to its right child.

We start inserting nodes from left to right based on their values. Let’s follow this process:

• The first value is 3. Since it is less than 5 (the root node), we move to the left child of 5.
• The second value is 8. Since it is greater than or equal to 5, we move to the right child of 5.
• The third value is 1. Since it is less than 5, we move to the left child of 5. Now, since there is no left child available, we insert 1 as the left child of 3.
• The fourth value is 4. Since it is greater than or equal to 3, we move to the right child of 3.

  Now, since there is no right child available, we insert 4 as the right child of 3.

• The fifth value is 7. Since it is less than 8, we move to the left child of 8. Now, since there is no left child available, we insert 7 as the left child of 8.
• The sixth value is 10. Since it is greater than or equal to 8 (the current node), we move to its right child. Now, since there is no right child available, we insert 10 as the right child of 8.

After inserting all the nodes based on their values, our binary search tree looks like this:

          5
         / \
        /   \
       /     \
      /       \
    3     8
   / \     / \
 1  4  7   10

This structure allows for efficient searching, insertion, and deletion of values. When searching for a value in a binary search tree, we compare it with the current node’s value and move left or right accordingly until we find the desired value or determine that it does not exist in the tree.

In conclusion, a binary search tree is a valuable data structure that provides fast access and manipulation of data. It is widely used in various applications such as searching, sorting, and indexing. Understanding the concept and implementation of binary search trees is essential for any programmer or computer science enthusiast.