 # Binary Search Tree in Data Structures

Amit Kumar Ghosh  59 min read
12 Sep 2023
Beginner
411 Views

## Binary Search Tree in Data Structure: An Overview

Data structures are the building blocks of computer programming. They help us to organize, store, and access data efficiently. One such important data structure is called a binary search tree (BST). A BST helps us store structured data in an organized fashion while allowing us to efficiently find elements within that structure. In this article, we'll go into detail about how BSTs work and why they have become so popular among developers! We'll cover topics like what a Binary Search Tree actually is, its advantages and disadvantages compared to other similar data structures, how it works through example scenarios, ways you can implement them in your codebase as well as any caveats or watch-outs when using these heavily in production applications. Stay tuned for more details on this powerful data structure!

## What is a binary search tree in data structure? A binary search tree is a foundational data structure for searching and sorting data in computer science. Binary search tree in data structure is a particular type of tree composed of nodes, with each node having up to two child nodes. The tree is arranged in such a way that each node's value is greater than all of its left-child descendants and less than all of its right-child descendants. This property allows for efficient searching, as data can be quickly compared to the values of nodes to determine which direction to traverse the tree. Binary search tree in data structure are used in a wide range of applications, from database management systems to search engines. Understanding this fundamental data structure is essential for any computer science student or software developer.

## Properties of Binary Search Tree

1. Each node in the tree has at most two children, referred to as the left child and the right child.
2. The keys in the left subtree of a node are less than the keys in the node.
3. The keys in the right subtree of a node are greater than the key in the node.
4. The left and right subtrees themselves are also binary search trees.
5. The keys in a binary search tree are unique.

## Binary search tree operations

The binary search tree operations are,

### Insertion

To insert an element in a BST, the user can start at the root node and compare the value of the new element with the value of the root. If the new element is less than the root, move to the left child node and repeat the comparison process. If the new element is greater than the root, move to the right child node and repeat the comparison process. The developer continues this process until they reach a leaf node where the new element can be inserted as a new child node.

#### Algorithm

1. Start at the root of the tree.
2. If the tree is empty, create a new node and make it the root.
3. If the value of the new node is less than the value of the current node, move to the left child of the current node.
4. If the value of the new node is greater than the value of the current node, move to the right child of the current node.
5. Repeat steps 3 and 4 until a leaf node is reached.
Create a new node with the value to be inserted and attach it as the left or right child of the leaf node reached in step 5, depending on whether its value is less than or greater than the value of the leaf node.
``````
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Function to insert a new node in the binary search tree
def insertNode(root, value):
if root is None:
root = Node(value)
return root
if value < root.value:
root.left = insertNode(root.left, value)
else:
root.right = insertNode(root.right, value)
return root
# Function to print the binary search tree in inorder traversal
def printInorder(root):
if root is None:
return
printInorder(root.left)
print(root.value, end=' ')
printInorder(root.right)
root = None
n = int(input("Enter the number of nodes: "))
for i in range(n):
value = int(input("Enter the value of node {}: ".format(i+1)))
root = insertNode(root, value)
print("The binary search tree in inorder traversal:", end=' ')
printInorder(root)``````
``````
import java.util.Scanner;
class Node {
int value;
Node left;
Node right;
}
public class Main {
// Function to create a new node
public static Node createNode(int value) {
Node newNode = new Node();
newNode.value = value;
newNode.left = null;
newNode.right = null;
return newNode;
}
// Function to insert a new node in the binary search tree
public static Node insertNode(Node root, int value) {
if (root == null) {
root = createNode(value);
return root;
}
if (value < root.value) {
root.left = insertNode(root.left, value);
} else {
root.right = insertNode(root.right, value);
}
return root;
}
// Function to print the binary search tree in inorder traversal
public static void printInorder(Node root) {
if (root == null) {
return;
}
printInorder(root.left);
System.out.print(root.value + " ");
printInorder(root.right);
}
public static void main(String[] args) {
Node root = null;
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number of nodes: ");
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
System.out.print("Enter the value of node " + (i+1) + ": ");
int value = sc.nextInt();
root = insertNode(root, value);
}
System.out.print("The binary search tree in inorder traversal: ");
printInorder(root);
}
}``````
``````
#include <iostream>
using namespace std;
struct Node {
int value;
Node* left;
Node* right;
};
// Function to create a new node
Node* createNode(int value) {
Node* newNode = new Node;
newNode->value = value;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}
// Function to insert a new node in the binary search tree
Node* insertNode(Node* root, int value) {
if (root == nullptr) {
root = createNode(value);
return root;
}
if (value < root->value) {
root->left = insertNode(root->left, value);
}
else {
root->right = insertNode(root->right, value);
}
return root;
}
// Function to print the binary search tree in inorder traversal
void printInorder(Node* root) {
if (root == nullptr) {
return;
}
printInorder(root->left);
cout << root->value << " ";
printInorder(root->right);
}
int main() {
Node* root = nullptr;
int n, value;
cout << "Enter the number of nodes: ";
cin >> n;
for (int i = 0; i < n; i++) {
cout << "Enter the value of node " << i + 1 << ": ";
cin >> value;
root = insertNode(root, value);
}
cout << "The binary search tree in inorder traversal: ";
printInorder(root);
return 0;
}``````

#### Output

``` ```Enter the number of nodes: 5
Enter the value of node 1: 3
Enter the value of node 2: 1
Enter the value of node 3: 4
Enter the value of node 4: 2
Enter the value of node 5: 5
The binary search tree in inorder traversal: 1 2 3 4 5``````

### Search

To search for an element in a BST, the user starts at the root node and compares the value of the element with the value of the root. If the value matches have found the element. If the value is less than the root, move to the left child node and repeat the comparison process. If the value is greater than the root, move to the right child node and repeat the comparison process. The developer continues this process until they find the element or reach a leaf node where the element does not exist.

#### Algorithm

1. Start from the root node.
2. If the root node is null, the tree is empty, and the search is unsuccessful.
3. If the search value is equal to the value of the current node, return the current node.
4. If the search value is less than the value of the current node, go to the left child node.
5. If the search value is greater than the value of the current node, go to the right child node.
6. Repeat steps 3 to 5 until the search value is found or the current node is null.
``````
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def search(root, key):
if root is None or root.data == key:
return root
if root.data < key:
return search(root.right, key)
return search(root.left, key)
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)
key = 60
result = search(root, key)
if result is not None:
print("Found:", result.data)
else:
``````
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}
public class Main {
static Node newNode(int data) {
Node node = new Node(data);
return node;
}
static Node search(Node root, int key) {
if (root == null || root.data == key)
return root;
if (root.data < key)
return search(root.right, key);
return search(root.left, key);
}
public static void main(String[] args) {
Node root = newNode(50);
root.left = newNode(30);
root.right = newNode(70);
root.left.left = newNode(20);
root.left.right = newNode(40);
root.right.left = newNode(60);
root.right.right = newNode(80);
int key = 60;
Node result = search(root, key);
if (result != null)
System.out.println("Found: " + result.data);
else
}
}``````
``````
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* newNode(int data) {
Node* node = new Node();
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
Node* search(Node* root, int key) {
if (root == NULL || root->data == key)
return root;
if (root->data < key)
return search(root->right, key);
return search(root->left, key);
}
int main() {
Node* root = newNode(50);
root->left = newNode(30);
root->right = newNode(70);
root->left->left = newNode(20);
root->left->right = newNode(40);
root->right->left = newNode(60);
root->right->right = newNode(80);
int key = 60;
Node* result = search(root, key);
if (result != NULL)
cout << "Found: " << result->data << endl;
else
return 0;
}``````

#### Output

` `Found: 60``

### Deletion

To delete an element from a BST, the user first search for the element using the search operation. If the element is found, there are three cases to consider:

#### Algorithm

1. The node to be deleted has no children: In this case, simply remove the node from the tree.
2. The node to be deleted has one child: In this case, remove the node from the tree and replace it with its child.
3. The node to be deleted has two children: In this case, find the minimum value node in the right subtree (or the maximum value node in the left subtree) and replace the node to be deleted with this node. Then delete the minimum (or maximum) value node from the subtree.
``````
# BST node class
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Function to delete a node from BST
def deleteNode(root, key):
# Base case
if root is None:
return root
# If the key to be deleted is smaller than the root's key,
# then it lies in the left subtree
if key < root.key:
root.left = deleteNode(root.left, key)
# If the key to be deleted is greater than the root's key,
# then it lies in the right subtree
elif key > root.key:
root.right = deleteNode(root.right, key)
# If key is same as root's key, then this is the node to be deleted
else:
# Node with only one child or no child
if root.left is None:
temp = root.right
del root
return temp
elif root.right is None:
temp = root.left
del root
return temp
# Node with two children: Get the inorder successor (smallest in the right subtree)
temp = root.right
while temp.left is not None:
temp = temp.left
# Copy the inorder successor's content to this node
root.key = temp.key
# Delete the inorder successor
root.right = deleteNode(root.right, temp.key)
return root
# Function to insert a node into BST
def insertNode(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insertNode(root.left, key)
else:
root.right = insertNode(root.right, key)
return root
# Function to print inorder traversal of BST
def inorderTraversal(root):
if root is not None:
inorderTraversal(root.left)
print(root.key, end=" ")
inorderTraversal(root.right)
# Driver code
if __name__ == "__main__":
root = None
root = insertNode(root, 50)
root = insertNode(root, 30)
root = insertNode(root, 20)
root = insertNode(root, 40)
root = insertNode(root, 70)
root = insertNode(root, 60)
root = insertNode(root, 80)
print("Inorder traversal of the original tree:", end=" ")
inorderTraversal(root)
print()
root = deleteNode(root, 20)
print("Inorder traversal after deleting 20:", end=" ")
inorderTraversal(root)
print()
root = deleteNode(root, 30)
print("Inorder traversal after deleting 30:", end=" ")
inorderTraversal(root)
print()
root = deleteNode(root, 50)
print("Inorder traversal after deleting 50:", end=" ")
inorderTraversal(root)
print()``````
``````
class Node {
int key;
Node left, right;
Node(int data) {
key = data;
left = right = null;
}
}
class BST {
// Function to delete a node from BST
public static Node deleteNode(Node root, int key) {
// Base case
if (root == null) {
return root;
}
// If the key to be deleted is smaller than the root's key,
// then it lies in the left subtree
if (key < root.key) {
root.left = deleteNode(root.left, key);
}
// If the key to be deleted is greater than the root's key,
// then it lies in the right subtree
else if (key > root.key) {
root.right = deleteNode(root.right, key);
}
// If key is same as root's key, then this is the node to be deleted
else {
// Node with only one child or no child
if (root.left == null) {
Node temp = root.right;
root = null;
return temp;
} else if (root.right == null) {
Node temp = root.left;
root = null;
return temp;
}
// Node with two children: Get the inorder successor (smallest in the right subtree)
Node temp = root.right;
while (temp.left != null) {
temp = temp.left;
}
// Copy the inorder successor's content to this node
root.key = temp.key;
// Delete the inorder successor
root.right = deleteNode(root.right, temp.key);
}
return root;
}
// Function to insert a node into BST
public static Node insertNode(Node root, int key) {
if (root == null) {
return new Node(key);
}
if (key < root.key) {
root.left = insertNode(root.left, key);
} else {
root.right = insertNode(root.right, key);
}
return root;
}
// Function to print inorder traversal of BST
public static void inorderTraversal(Node root) {
if (root != null) {
inorderTraversal(root.left);
System.out.print(root.key + " ");
inorderTraversal(root.right);
}
}
// Driver code
public static void main(String[] args) {
Node root = null;
root = insertNode(root, 50);
root = insertNode(root, 30);
root = insertNode(root, 20);
root = insertNode(root, 40);
root = insertNode(root, 70);
root = insertNode(root, 60);
root = insertNode(root, 80);
System.out.print("Inorder traversal of the original tree: ");
inorderTraversal(root);
System.out.println();
root = deleteNode(root, 20);
System.out.print("Inorder traversal after deleting 20: ");
inorderTraversal(root);
System.out.println();
root = deleteNode(root, 30);
System.out.print("Inorder traversal after deleting 30: ");
inorderTraversal(root);
System.out.println();
root = deleteNode(root, 50);
System.out.print("Inorder traversal after deleting 50: ");
inorderTraversal(root);
System.out.println();
}
}``````
``````
#include <iostream>
using namespace std;
// BST node structure
struct Node {
int key;
Node* left;
Node* right;
Node(int data) {
key = data;
left = right = NULL;
}
};
// Function to delete a node from BST
Node* deleteNode(Node* root, int key) {
// Base case
if (root == NULL) {
return root;
}
// If the key to be deleted is smaller than the root's key,
// then it lies in the left subtree
if (key < root->key) {
root->left = deleteNode(root->left, key);
}
// If the key to be deleted is greater than the root's key,
// then it lies in the right subtree
else if (key > root->key) {
root->right = deleteNode(root->right, key);
}
// If key is same as root's key, then this is the node to be deleted
else {
// Node with only one child or no child
if (root->left == NULL) {
Node* temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL) {
Node* temp = root->left;
delete root;
return temp;
}
// Node with two children: Get the inorder successor (smallest in the right subtree)
Node* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
// Copy the inorder successor's content to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
// Function to insert a node into BST
Node* insertNode(Node* root, int key) {
if (root == NULL) {
return new Node(key);
}
if (key < root->key) {
root->left = insertNode(root->left, key);
}
else {
root->right = insertNode(root->right, key);
}
return root;
}
// Function to print inorder traversal of BST
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
cout << root->key << " ";
inorderTraversal(root->right);
}
}
// Driver code
int main() {
Node* root = NULL;
root = insertNode(root, 50);
root = insertNode(root, 30);
root = insertNode(root, 20);
root = insertNode(root, 40);
root = insertNode(root, 70);
root = insertNode(root, 60);
root = insertNode(root, 80);
cout << "Inorder traversal of the original tree: ";
inorderTraversal(root);
cout << endl;
root = deleteNode(root, 20);
cout << "Inorder traversal after deleting 20: ";
inorderTraversal(root);
cout << endl;
root = deleteNode(root, 30);
cout << "Inorder traversal after deleting 30: ";
inorderTraversal(root);
cout << endl;
root = deleteNode(root, 50);
cout << "Inorder traversal after deleting 50: ";
inorderTraversal(root);
cout << endl;
return 0;
}``````

#### Output

``` ```Inorder traversal of the original tree: 20 30 40 50 60 70 80
Inorder traversal after deleting 20: 30 40 50 60 70 80
Inorder traversal after deleting 30: 40 50 60 70 80
Inorder traversal after deleting 50: 40 60 70 80``````

### Traversal

Traversal refers to the process of visiting all nodes in a BST. There are three types of traversal:
• In-order traversal: In this traversal, the user visits the left subtree, then the root, and then the right subtree.

#### Algorithm

1. Traverse the left subtree in inorder.
2. Visit the root node.
3. Traverse the right subtree in inorder.
• Pre-order traversal: In this traversal, the user visits the root, then the left subtree, and then the right subtree.

#### Algorithm

1. Visit the root node.
2. Traverse the left subtree in preorder.
3. Traverse the right subtree in preorder.
• Post-order traversal: In this traversal, the user visits the left subtree, then the right subtree, and then the root.

#### Algorithm

1. Traverse the left subtree in postorder.
2. Traverse the right subtree in postorder.
3. Visit the root node.
``````# create an array
class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
def inorder(root):
if root is None:
return
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
def preorder(root):
if root is None:
return
print(root.data, end=" ")
preorder(root.left)
preorder(root.right)
def postorder(root):
if root is None:
return
postorder(root.left)
postorder(root.right)
print(root.data, end=" ")
if __name__ == "__main__":
# Create a sample binary search tree
root = Node(4)
root.left = Node(2)
root.right = Node(6)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(5)
root.right.right = Node(7)
# Traversal operations
print("Inorder traversal:", end=" ")
inorder(root)
print()
print("Preorder traversal:", end=" ")
preorder(root)
print()
print("Postorder traversal:", end=" ")
postorder(root)
print()``````
``````
class Node {
int data;
Node left, right;
public Node(int val) {
data = val;
left = right = null;
}
}
public class Main {
// Inorder traversal
static void inorder(Node root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
// Preorder traversal
static void preorder(Node root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// Postorder traversal
static void postorder(Node root) {
if (root == null) {
return;
}
postorder(root.left);
postorder(root.right);
System.out.print(root.data + " ");
}
public static void main(String[] args) {
// Create a sample binary search tree
Node root = new Node(4);
root.left = new Node(2);
root.right = new Node(6);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.left = new Node(5);
root.right.right = new Node(7);
// Traversal operations
System.out.print("Inorder traversal: ");
inorder(root);
System.out.println();
System.out.print("Preorder traversal: ");
preorder(root);
System.out.println();
System.out.print("Postorder traversal: ");
postorder(root);
System.out.println();
}
}``````
``````
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = NULL;
right = NULL;
}
};
// Inorder traversal
void inorder(Node* root) {
if (root == NULL) {
return;
}
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
// Preorder traversal
void preorder(Node* root) {
if (root == NULL) {
return;
}
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
// Postorder traversal
void postorder(Node* root) {
if (root == NULL) {
return;
}
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
int main() {
// Create a sample binary search tree
Node* root = new Node(4);
root->left = new Node(2);
root->right = new Node(6);
root->left->left = new Node(1);
root->left->right = new Node(3);
root->right->left = new Node(5);
root->right->right = new Node(7);
// Traversal operations
cout << "Inorder traversal: ";
inorder(root);
cout << endl;
cout << "Preorder traversal: ";
preorder(root);
cout << endl;
cout << "Postorder traversal: ";
postorder(root);
cout << endl;
return 0;
}``````

#### Output

``````Inorder traversal: 1 2 3 4 5 6 7
Preorder traversal: 4 2 1 3 6 5 7
Postorder traversal: 1 3 2 5 7 6 4 ``````

## Advantages of binary search tree

1. Efficient searching: One of the main advantages of BSTs is that they allow for very efficient searching of elements. Because of the way that data is stored in a BST, it is possible to search for an element in logarithmic time, which is much faster than searching through an unsorted array or list.
2. Sorted order: Another advantage of BSTs is that the elements are automatically sorted in the tree structure. This can be useful for applications where the user needs to maintain an ordered list of elements.
3. Easy to implement: BSTs are relatively easy to implement and can be built using simple recursive algorithms. This makes them a popular choice for developers who need to quickly implement data structures in their code.
4. Dynamic size: Unlike some other data structures, such as arrays or linked lists, BSTs can be easily resized to accommodate new elements as they are added to the structure.
5. Flexibility: BSTs can be used to implement a wide range of other data structures, such as sets, maps, and priority queues, making them a versatile choice for many different programming applications.

## Disadvantages of binary search tree

1. Unbalanced trees: If a binary search tree is not properly balanced, its performance can become worse than O(log n) for searching and insertion operations, as these operations may need to traverse the entire height of the tree.
2. Inefficient for large datasets: For very large datasets, BSTs may not be the best choice for storage and retrieval, as the tree height can become very large, and the space complexity of the tree can become an issue.
3. Degenerate trees: A degenerate binary search tree is one in which each node has only one child, and the tree degenerates into a linked list. In such cases, searching and insertion operations can become O(n), which makes the BST less efficient than other data structures.
4. Vulnerable to skewness: If the elements of a binary search tree are inserted in a specific order (such as already sorted), the tree may become skewed, with one branch becoming very long and the other very short, leading to unbalanced trees and affecting the performance.
5. Inefficient for range queries: BSTs are not very efficient for range queries, as they require traversing the entire tree to find all nodes within a certain range, unlike other data structures such as B-trees or AVL trees.

## The complexity of the Binary Search tree (time and space complexity in data structure)

### Time Complexity of Binary search tree

 Operations Best-case time complexity Average case time complexity Worst-case time complexity Insertion O(log n) O(log n) O(n) Deletion O(log n) O(log n) O(n) Search O(log n) O(log n) O(n)

#### Space complexity of binary search tree

 Operations Space complexity Insertion O(n) Deletion O(n) Search O(n)

## What are the Real-World Applications of Binary Search Trees?

1. Databases: Many databases use BSTs to store and search for data. For example, MySQL and SQLite use BSTs to store indexes of the data they contain, making queries much faster.
2. File Systems: File systems use BSTs to store and organize files on a hard drive. For example, the Windows NTFS file system uses BSTs to store the Master File Table (MFT), which contains information about all the files on the hard drive.
3. Computer Networks: BSTs can be used to store routing tables in computer networks. This allows routers to quickly find the best route for a packet to take from one network to another.
4. Sorting: BSTs can be used as a sorting algorithm. By inserting elements in a BST and then traversing it in order, the elements can be sorted in O(nlogn) time.
5. Language Modeling: BSTs can be used to store n-grams in natural language processing tasks. This allows for efficient searching of the most common n-grams, making language modeling tasks faster.
6. Machine Learning: BSTs can be used in decision tree-based machine learning algorithms, where the decision tree is a binary search tree that makes decisions based on the input features.
7. Game Trees: BSTs can be used to represent game trees in game theory, allowing for efficient searching of possible game states and moves.
##### Summary
In conclusion, binary search trees are an incredibly useful tool in data structure and should not be overlooked. Using them efficiently is a skill all computer scientists should master. With enough practice, you too can interpret this complex construct with ease. Implementing the binary search tree properly allows you to maximize efficiency while searching through data structures far more quickly than other methods. Being aware of the ways you can explore your data through a binary search tree will give you an edge when dealing with complex information architectures. If you're looking for an efficient way to traverse through data structures, investing time in learning about binary search trees is certainly worth it! We hope this article has given you enough insight into the inner workings of a binary search tree in a data structure so that you can confidently make use of its capabilities!
Similar Articles 