Binary Search Tree (BST) Code Implementations
Production-ready Binary Search Tree (BST) data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.
Study Binary Search Tree (BST) Guide ยท Launch Visualizer
CPP Implementation
// Binary Search Tree Implementation in Java
class BinarySearchTree {
// Node structure
static class Node {
int data;
Node left, right;
Node(int val) {
data = val;
left = right = null;
}
}
Node root;
BinarySearchTree() {
root = null;
}
// Insert a node
Node insert(Node node, int val) {
if (node == null) {
return new Node(val);
}
if (val < node.data) {
node.left = insert(node.left, val);
} else if (val > node.data) {
node.right = insert(node.right, val);
}
return node;
}
void insert(int val) {
root = insert(root, val);
}
// Search for a value
boolean search(Node node, int val) {
if (node == null) return false;
if (node.data == val) return true;
if (val < node.data)
return search(node.left, val);
else
return search(node.right, val);
}
boolean search(int val) {
return search(root, val);
}
// Delete a node
Node delete(Node node, int val) {
if (node == null) return null;
if (val < node.data) {
node.left = delete(node.left, val);
} else if (val > node.data) {
node.right = delete(node.right, val);
} else {
// Case 1: Node with only one child or no child
if (node.left == null) return node.right;
else if (node.right == null) return node.left;
// Case 2: Node with two children -> inorder successor
node.data = minValue(node.right);
node.right = delete(node.right, node.data);
}
return node;
}
void delete(int val) {
root = delete(root, val);
}
int minValue(Node node) {
int min = node.data;
while (node.left != null) {
min = node.left.data;
node = node.left;
}
return min;
}
// Inorder Traversal (Left, Root, Right)
void inorder(Node node) {
if (node == null) return;
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}
void inorder() {
inorder(root);
System.out.println();
}
// Preorder Traversal (Root, Left, Right)
void preorder(Node node) {
if (node == null) return;
System.out.print(node.data + " ");
preorder(node.left);
preorder(node.right);
}
void preorder() {
preorder(root);
System.out.println();
}
// Postorder Traversal (Left, Right, Root)
void postorder(Node node) {
if (node == null) return;
postorder(node.left);
postorder(node.right);
System.out.print(node.data + " ");
}
void postorder() {
postorder(root);
System.out.println();
}
// Main method
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// Insert nodes
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
System.out.print("Inorder Traversal: ");
bst.inorder();
System.out.print("Preorder Traversal: ");
bst.preorder();
System.out.print("Postorder Traversal: ");
bst.postorder();
System.out.println("Search 40: " + (bst.search(40) ? "Found" : "Not Found"));
System.out.println("Search 25: " + (bst.search(25) ? "Found" : "Not Found"));
System.out.println("Deleting 20...");
bst.delete(20);
bst.inorder();
System.out.println("Deleting 30...");
bst.delete(30);
bst.inorder();
System.out.println("Deleting 50...");
bst.delete(50);
bst.inorder();
}
}