Introduction to Binary Search Tree(BST)
A Binary Search Tree (BST) is a specialized data structure used in computer science to organize and store data in a sorted manner. It follows the properties of a binary tree, where each node has at most two children. In a BST, the left subtree of a node contains values less than the node, while the right subtree contains values greater than the node. This hierarchical structure enables efficient searching, insertion, and deletion operations, making BSTs widely used in applications requiring fast data retrieval
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.
Key Properties That Distinguish a Binary Search Tree from a Regular Binary Tree
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
- Start at the root node.
- If the root is None, the target is not in the tree.
- 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.
- 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:
- Start at the root (8): 7 is less than 8, so move to the left child (3).
- At node 3: 7 is greater than 3, so move to the right child (6).
- At node 6: 7 is greater than 6, so move to the right child (7).
- 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;
}
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;
}
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.");
}
}
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.")
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.
132+ registered 
