Algorithm
A Binary Search Tree (BST) is a binary tree data structure with the following properties:
-
Binary Tree Structure: Each node in a BST has at most two children, which are referred to as the left child and the right child.
-
Value Ordering: For each node in the tree, all nodes in its left subtree have values less than the node's value, and all nodes in its right subtree have values greater than the node's value. This ordering property ensures that the BST is a useful data structure for searching, insertion, and deletion operations.
Here's a simple example of a Binary Search Tree:
markdown
5
/ \
3 8
/ \ / \
1 4 7 9
In this example, for any node, the values in its left subtree are less than the node's value, and the values in its right subtree are greater than the node's value.
Operations on a Binary Search Tree:
-
Search:
- Start at the root node.
- If the target value is equal to the current node's value, return the node.
- If the target value is less than the current node's value, search in the left subtree.
- If the target value is greater than the current node's value, search in the right subtree.
-
Insertion:
- Search for the value as you would in the search operation.
- If the value is not found, insert a new node with the given value at the appropriate position according to the BST property.
-
Deletion:
- Search for the node to be deleted.
- If the node has no children, simply remove it.
- If the node has one child, replace it with its child.
- If the node has two children, find the node's in-order successor (or predecessor), replace the node's value with the successor's (or predecessor's) value, and recursively delete the successor (or predecessor).
Time Complexity:
- Search, Insertion, and Deletion: O(log n) on average, where n is the number of nodes in the tree.
- In the worst case (unbalanced tree), these operations can degrade to O(n), but maintaining balance (e.g., using a self-balancing BST like AVL tree or Red-Black tree) helps avoid this scenario.
Binary Search Trees are commonly used in computer science due to their efficient search and insertion operations, making them suitable for a variety of applications, including databases and symbol tables.
Code Examples
#1 Binary Search Tree(BST) implement in Python
Code -
Python Programming
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, key):
self.root = self._insert(self.root, key)
def _insert(self, root, key):
if root is None:
return TreeNode(key)
if key < root.key:
root.left = self._insert(root.left, key)
elif key > root.key:
root.right = self._insert(root.right, key)
return root
def search(self, key):
return self._search(self.root, key)
def _search(self, root, key):
if root is None or root.key == key:
return root
if key < root.key:
return self._search(root.left, key)
else:
return self._search(root.right, key)
def inorder_traversal(self):
result = []
self._inorder_traversal(self.root, result)
return result
def _inorder_traversal(self, root, result):
if root:
self._inorder_traversal(root.left, result)
result.append(root.key)
self._inorder_traversal(root.right, result)
# Example usage:
bst = BST()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)
print("Inorder Traversal:", bst.inorder_traversal())
search_key = 40
search_result = bst.search(search_key)
if search_result:
print(f"Key {search_key} found in the BST.")
else:
print(f"Key {search_key} not found in the BST.")
#2 Binary Search Tree(BST) implement in Java
Code -
Java Programming
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
public class BinarySearchTree {
private Node root;
public BinarySearchTree() {
root = null;
}
// Insert a key into the BST
public void insert(int key) {
root = insertRec(root, key);
}
private Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key) {
root.left = insertRec(root.left, key);
} else if (key > root.key) {
root.right = insertRec(root.right, key);
}
return root;
}
// Delete a key from the BST
public void delete(int key) {
root = deleteRec(root, key);
}
private Node deleteRec(Node root, int key) {
if (root == null) {
return root;
}
if (key < root.key) {
root.left = deleteRec(root.left, key);
} else if (key > root.key) {
root.right = deleteRec(root.right, key);
} else {
// Node with only one child or no child
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}
// Node with two children: Get the inorder successor (smallest in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(root.right, root.key);
}
return root;
}
private int minValue(Node root) {
int minValue = root.key;
while (root.left != null) {
minValue = root.left.key;
root = root.left;
}
return minValue;
}
// In-order traversal
public void inOrderTraversal() {
inOrderTraversalRec(root);
}
private void inOrderTraversalRec(Node root) {
if (root != null) {
inOrderTraversalRec(root.left);
System.out.print(root.key + " ");
inOrderTraversalRec(root.right);
}
}
// Pre-order traversal
public void preOrderTraversal() {
preOrderTraversalRec(root);
}
private void preOrderTraversalRec(Node root) {
if (root != null) {
System.out.print(root.key + " ");
preOrderTraversalRec(root.left);
preOrderTraversalRec(root.right);
}
}
// Post-order traversal
public void postOrderTraversal() {
postOrderTraversalRec(root);
}
private void postOrderTraversalRec(Node root) {
if (root != null) {
postOrderTraversalRec(root.left);
postOrderTraversalRec(root.right);
System.out.print(root.key + " ");
}
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// Insert keys
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);
// Print in-order traversal
System.out.println("In-order traversal:");
bst.inOrderTraversal();
System.out.println();
// Print pre-order traversal
System.out.println("Pre-order traversal:");
bst.preOrderTraversal();
System.out.println();
// Print post-order traversal
System.out.println("Post-order traversal:");
bst.postOrderTraversal();
System.out.println();
// Delete a key
bst.delete(20);
// Print in-order traversal after deletion
System.out.println("In-order traversal after deletion:");
bst.inOrderTraversal();
System.out.println();
}
}
#3 Binary Search Tree(BST) implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Node structure for the Binary Search Tree
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to insert a value into the BST
struct Node* insert(struct Node* root, int value) {
// If the tree is empty, create a new node and return it
if (root == NULL) {
return createNode(value);
}
// Otherwise, recur down the tree
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
// Return the (unchanged) node pointer
return root;
}
// Function to perform an in-order traversal of the BST
void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// Function to search for a value in the BST
struct Node* search(struct Node* root, int value) {
// Base Cases: root is null or value is present at root
if (root == NULL || root->data == value) {
return root;
}
// Value is smaller than root's key
if (value < root->data) {
return search(root->left, value);
}
// Value is larger than root's key
return search(root->right, value);
}
int main() {
struct Node* root = NULL;
// Insert elements into the BST
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
// Print in-order traversal of the BST
printf("In-order traversal: ");
inorderTraversal(root);
printf("\n");
// Search for a value in the BST
int searchValue = 40;
struct Node* result = search(root, searchValue);
if (result != NULL) {
printf("%d found in the BST.\n", searchValue);
} else {
printf("%d not found in the BST.\n", searchValue);
}
return 0;
}
#4 Binary Search Tree(BST) implement in C++
Code -
C++ Programming
#include <iostream>
class TreeNode {
public:
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};
class BinarySearchTree {
private:
TreeNode* root;
// Helper function to insert a value into the tree
TreeNode* insert(TreeNode* node, int value) {
if (node == nullptr) {
return new TreeNode(value);
}
if (value < node->data) {
node->left = insert(node->left, value);
} else if (value > node->data) {
node->right = insert(node->right, value);
}
return node;
}
// Helper function to perform in-order traversal
void inorderTraversal(TreeNode* node) {
if (node != nullptr) {
inorderTraversal(node->left);
std::cout << node->data << " ";
inorderTraversal(node->right);
}
}
public:
BinarySearchTree() : root(nullptr) {}
// Function to insert a value into the tree
void insert(int value) {
root = insert(root, value);
}
// Function to perform in-order traversal of the tree
void inorderTraversal() {
inorderTraversal(root);
std::cout << std::endl;
}
};
int main() {
BinarySearchTree bst;
// Insert values into the tree
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
// Perform in-order traversal
std::cout << "In-order traversal: ";
bst.inorderTraversal();
return 0;
}
Demonstration
Binary Search Tree(BST)-DevsEnv