Table of contents
1.
What is Binary Search Tree?
2.
Search Operation in Binary Search Tree
2.1.
Algorithm
2.2.
Implementation
2.3.
C
2.4.
C++
2.5.
Java
2.6.
Python
3.
Inserting a node into Binary Search Tree 
4.
Deleting a node from a Binary Search Tree
4.1.
1. ‘N’ has no children
4.2.
2. ‘N’ has one child
4.3.
3. ‘N’ has two children
5.
Complexity of the Binary Search tree
6.
Implementation of Binary Search Tree
7.
Frequently Asked Questions
7.1.
How many maximum children can each Binary Search Tree node have?
7.2.
What is the method to find the immediate predecessor?
7.3.
What is a key in a binary search tree?
7.4.
Why is it called a binary search tree?
8.
Conclusion
Last Updated: Sep 22, 2024
Easy

Binary Search Trees

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

What is Binary Search Tree?

A binary Search Tree is a classification of Trees in which every node in the tree can have at most two children, the left child, and the right child. The data of the right child and the left child must be greater and smaller than the data of the parent node, respectively.

Binary Search Trees

The properties that separate a binary search tree from a regular binary tree:

  • Order Property: In a BST, for each node, the left subtree contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key. This is not required for a regular binary tree.
  • No Duplicate Keys: Typically, BSTs do not allow duplicate keys. Each key must be unique and placed in a specific order as per the BST property. A regular binary tree can have duplicate keys.
  • Efficient Search Operations: Due to the ordered nature of a BST, search operations (as well as insertions and deletions) can be performed more efficiently, often in O(log n) time for balanced trees. Regular binary trees do not have this order, making search operations potentially less efficient, with a time complexity of O(n) in the worst case.

Lets us see an example of a binary search tree.

In this BST, we can observe that the left child of every node has a value less than its parent node, and the right child of every node has a value greater than its parent node.

Search Operation in Binary Search Tree

The search operation in a BST takes advantage of the tree's ordered structure. Starting at the root, the algorithm compares the target value to the current node's value. If they match, the search is successful. If the target is less than the current node's value, the algorithm recurses into the left subtree; if greater, it recurses into the right subtree. This process continues until the target is found or a leaf node is reached, indicating that the target is not in the tree.

Algorithm

  1. Start at the root node.
  2. If the root is None, the target is not in the tree.
  3. Compare the target value with the value of the current node:
    • If equal, the target is found.
    • If less, move to the left child and repeat the process.
    • If greater, move to the right child and repeat the process.
  4. If a leaf node is reached and the target is not found, the target is not in the tree.

Consider the following BST:

8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

To search for the value 7:

  1. Start at the root (8): 7 is less than 8, so move to the left child (3).
  2. At node 3: 7 is greater than 3, so move to the right child (6).
  3. At node 6: 7 is greater than 6, so move to the right child (7).
  4. At node 7: 7 is equal to 7, so the target is found.

Implementation

  • C
  • C++
  • Java
  • Python

C

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
int value;
struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int key) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->value = key;
newNode->left = newNode->right = NULL;
return newNode;
}

TreeNode* insert(TreeNode* node, int key) {
if (node == NULL) return createNode(key);

if (key < node->value)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);

return node;
}

TreeNode* search(TreeNode* root, int key) {
if (root == NULL || root->value == key)
return root;

if (root->value < key)
return search(root->right, key);

return search(root->left, key);
}

int main() {
TreeNode* root = NULL;
root = insert(root, 8);
insert(root, 3);
insert(root, 10);
insert(root, 1);
insert(root, 6);
insert(root, 4);
insert(root, 7);
insert(root, 14);
insert(root, 13);

int target = 7;
TreeNode* result = search(root, target);
if (result != NULL)
printf("Value %d found in the BST.\n", target);
else
printf("Value %d not found in the BST.\n", target);

return 0;
}
You can also try this code with Online C Compiler
Run Code

C++

#include <iostream>
using namespace std;

class TreeNode {
public:
int value;
TreeNode *left, *right;

TreeNode(int key) {
value = key;
left = right = nullptr;
}
};

TreeNode* insert(TreeNode* node, int key) {
if (node == nullptr) return new TreeNode(key);

if (key < node->value)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);

return node;
}

TreeNode* search(TreeNode* root, int key) {
if (root == nullptr || root->value == key)
return root;

if (root->value < key)
return search(root->right, key);

return search(root->left, key);
}

int main() {
TreeNode* root = nullptr;
root = insert(root, 8);
insert(root, 3);
insert(root, 10);
insert(root, 1);
insert(root, 6);
insert(root, 4);
insert(root, 7);
insert(root, 14);
insert(root, 13);

int target = 7;
TreeNode* result = search(root, target);
if (result != nullptr)
cout << "Value " << target << " found in the BST." << endl;
else
cout << "Value " << target << " not found in the BST." << endl;

return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Java

class TreeNode {
int value;
TreeNode left, right;

public TreeNode(int item) {
value = item;
left = right = null;
}
}

class BinarySearchTree {
TreeNode root;

TreeNode insert(TreeNode node, int value) {
if (node == null) {
node = new TreeNode(value);
return node;
}

if (value < node.value)
node.left = insert(node.left, value);
else if (value > node.value)
node.right = insert(node.right, value);

return node;
}

TreeNode search(TreeNode root, int key) {
if (root == null || root.value == key)
return root;

if (root.value < key)
return search(root.right, key);

return search(root.left, key);
}

public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();

tree.root = tree.insert(tree.root, 8);
tree.insert(tree.root, 3);
tree.insert(tree.root, 10);
tree.insert(tree.root, 1);
tree.insert(tree.root, 6);
tree.insert(tree.root, 4);
tree.insert(tree.root, 7);
tree.insert(tree.root, 14);
tree.insert(tree.root, 13);

int target = 7;
TreeNode result = tree.search(tree.root, target);
if (result != null)
System.out.println("Value " + target + " found in the BST.");
else
System.out.println("Value " + target + " not found in the BST.");
}
}
You can also try this code with Online Java Compiler
Run Code

Python

class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.value = key

def search_bst(root, target):
if root is None or root.value == target:
return root

if target > root.value:
return search_bst(root.right, target)

return search_bst(root.left, target)

def insert(root, key):
if root is None:
return TreeNode(key)

if key < root.value:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)

return root

# Example usage
root = TreeNode(8)
root = insert(root, 3)
root = insert(root, 10)
root = insert(root, 1)
root = insert(root, 6)
root = insert(root, 4)
root = insert(root, 7)
root = insert(root, 14)
root = insert(root, 13)

target = 7
result = search_bst(root, target)
if result:
print(f"Value {target} found in the BST.")
else:
print(f"Value {target} not found in the BST.")
You can also try this code with Online Python Compiler
Run Code

Output

Value 7 found in the BST.

 

This code defines a TreeNode class and two functions: search_bst for searching a value in a BST, and insert for inserting new values into the BST. The example usage demonstrates creating a BST and searching for a value within it.

Now let us understand the procedure to insert and delete a node into the Binary Search Tree.

Inserting a node into Binary Search Tree 

Consider a Binary Search Tree ‘T’ and an arbitrary node ‘N’ having value stored as ‘Val’.  Below is the procedure to insert the node ‘N’ into ‘T’. 

  • First, we will compare the value ‘Val’ with the data stored in the root node. 
  • If ‘Val’ is greater than the root node's value, we will move to its right subtree.
  • If ‘Val’ is smaller than the root node's value, we will move to its left subtree.
  • We will repeat the first to third step until the current root node does not have left and right subtree. 
  • Now, if ‘Val’ is smaller than the value of the current root node, we will insert node ‘N’ as its left child.
  • Else if ‘Val’ is greater than the value of the current root node, we will insert node ‘N’ as its right child.

Now let us try inserting a node with ‘Val’ equal to 5 into the above tree.


Comparing the value ‘5’ from the value of the root and finding it to be greater, so moving to the right subtree. 

Comparing the value ‘5’ from the value of the current root and finding it to be smaller, so moving to the left subtree.

Comparing the value ‘5’ from the value of the current root and finding it to be greater, so moving to the right subtree.

On finding the current root without any subtree, we will insert the node ‘N’ as the right child.

Deleting a node from a Binary Search Tree

Let us consider a Binary Search Tree ‘T’ and the node to be deleted as ‘N’. Deletion of a node can be classified based on the number of children of the node to be deleted.  

1. ‘N’ has no children

When the node ‘N’ has no children, we can simply replace it will the null value.
For Example, the node with the value as ‘8’ is to be removed in the tree below.

Simply the node with the value ‘8’ can be removed.

2. ‘N’ has one child

When the node ‘N’ has only one child, we can replace it with its only child.
For Example, the node having the value as ‘4’ is removed in the below tree.

Simply the node with the value ‘4’ can be replaced with its only child, and then the replaced node will be removed.

3. ‘N’ has two children

When node ‘N’ has both children, we will need to determine the immediate predecessor. To find the immediate predecessor, we need to move to the left child of the node ‘N’ and then keep moving to the right child of the current node unless there is no right child. Then the node we have is the immediate predecessor. 

Now this immediate predecessor can be replaced with the node ‘N’. And then, the replaced node can be removed with the first or second method defined above accordingly. 
For Example, the node with the value as ‘7’ is to be removed in the tree below.

We will have to find its immediate predecessor to replace it with. The node with the value ‘5’ is the immediate predecessor with the above algorithm. 

The node ‘N’ will be replaced with the immediate predecessor.

And then, the replaced node will be removed.

Complexity of the Binary Search tree

Complexity of the Binary Search Tree

The time complexity of operations in a binary search tree (BST) depends on the height of the tree.

  • Best Case: For a balanced tree, where the height is logarithmic with respect to the number of nodes, the time complexity for search, insert, and delete operations is O(log n).
     
  • Average Case: Similarly, for a reasonably balanced tree, the average time complexity remains O(log n).
     
  • Worst Case: In the worst case, where the BST becomes unbalanced (like a linked list), the height becomes linear, leading to a time complexity of O(n) for search, insert, and delete operations.
     

Space complexity is O(n) for storing n nodes, as each node requires additional memory for its value and pointers.

Implementation of Binary Search Tree

The provided code implements a binary search tree (BST) that allows insertion and searching of values.

Example:
In the main function, we create a BST and insert the following values: 8, 3, 10, 1, 6, 4, 7, 14, and 13. The root of the tree starts as NULL. As we insert each value, the tree organizes itself according to BST properties: left child < Parent < Right child.

When searching for a value (in this case, 7), the program traverses the tree, comparing the target value with the current node's value and deciding whether to go left or right. If the target is found, a message is printed; otherwise, a message indicates that the value is not found.

This implementation efficiently maintains the structure of the BST and supports dynamic insertion and searching of values.

Frequently Asked Questions

How many maximum children can each Binary Search Tree node have?

The Binary Search Tree node can have a maximum of two children. The children are called left and right children.

What is the method to find the immediate predecessor?

To find the immediate predecessor, we need to move to the left child of the node ‘N’ and then keep moving to the right child of the current node unless there is no right child. Then the node we have is the immediate predecessor. 

What is a key in a binary search tree?

A key in a binary search tree is the value stored in a node, used to organize and compare nodes according to the tree's ordering properties, ensuring that left children are smaller and right children are larger.

Why is it called a binary search tree?

It is called a binary search tree because it combines the properties of a binary tree (each node has at most two children) with the ability to perform efficient search operations, due to its ordered structure.

Conclusion

In the above article, we have learned about Binary Search Trees. Binary Search Trees (BSTs) are fundamental data structures that provide efficient means for data storage, retrieval, and management. By leveraging the ordered nature of BSTs, we can perform search, insert, and delete operations with optimal efficiency, making them a preferred choice for many applications.

Recommended problems -

Live masterclass