Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.
It is called a binary tree because each tree node has a maximum of two children.
It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time.
The properties that separate a binary search tree from a regular binary tree is
(1) All nodes of left subtree are less than the root node
(2) All nodes of right subtree are more than the root node
(3) Both subtrees of each node are also BSTs i.e. they have the above two properties
import java.util.*;
// Binary Search Tree operations in Java
class BinarySearchTree {
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
Node root;
BinarySearchTree() {
root = null;
}
void insert(int key) {
root = insertKey(root, key);
}
// Insert key in the tree
Node insertKey(Node root, int key) {
// Return a new node if the tree is empty
if (root == null) {
root = new Node(key);
return root;
}
// Traverse to the right place and insert the node
if (key < root.key)
root.left = insertKey(root.left, key);
else if (key > root.key)
root.right = insertKey(root.right, key);
return root;
}
void inorder() {
inorderRec(root);
// Inorder Traversal
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " -> ");
inorderRec(root.right);
}
}
void deleteKey(int key) {
root = deleteRec(root, key);
}
Node deleteRec(Node root, int key) {
// Return if the tree is empty
if (root == null)
return root;
// Find the node to be deleted
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
else {
// If the node is with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// If the node has two children
// Place the inorder successor in position of the node to be deleted
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(root.right, root.key);
}
return root;
}
// Find the inorder successor
int minValue(Node root) {
int minv = root.key;
while (root.left != null) {
minv = root.left.key;
root = root.left;
}
return minv;
}
// Driver Program to test above functions
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(8);
tree.insert(3);
tree.insert(1);
tree.insert(6);
tree.insert(7);
tree.insert(10);
tree.insert(14);
tree.insert(4);
System.out.print("Inorder traversal: ");
tree.inorder();
System.out.println("\n\nAfter deleting 10");
tree.deleteKey(10);
System.out.print("Inorder traversal: ");
tree.inorder();
}
}
Best Case Time Complexity:O(log n)
Average Case Complexity:O(log n)
Worst Case Complexity:O(log n)
Best Case Time Complexity:O(log n)
Average Case Complexity:O(log n)
Worst Case Complexity:O(log n)
Best Case Time Complexity:O(log n)
Average Case Complexity:O(log n)
Worst Case Complexity:O(log n)
O(n)