Implementation of Binary Search Tree
// Java Program to Implement
// Binary Search Tree
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
class BinarySearchTree {
Node root;
public BinarySearchTree() {
root = null;
}
// Insertion operation
void insert(int key) {
root = insertRec(root, key);
}
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;
}
// Deletion operation
void delete(int key) {
root = deleteRec(root, key);
}
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 {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.key = minValue(root.right);
root.right = deleteRec(root.right, root.key);
}
return root;
}
int minValue(Node root) {
int minv = root.key;
while (root.left != null) {
minv = root.left.key;
root = root.left;
}
return minv;
}
// Search operation
boolean search(int key) {
return searchRec(root, key);
}
boolean searchRec(Node root, int key) {
if (root == null)
return false;
if (root.key == key)
return true;
if (root.key < key)
return searchRec(root.right, key);
return searchRec(root.left, key);
}
// Inorder traversal
void inorder() {
inorderRec(root);
System.out.println("\n");
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Preorder traversal
void preorder() {
preorderRec(root);
System.out.println("\n");
}
void preorderRec(Node root) {
if (root != null) {
System.out.print(root.key + " ");
preorderRec(root.left);
preorderRec(root.right);
}
}
// Postorder traversal
void postorder() {
postorderRec(root);
System.out.println("\n");
}
void postorderRec(Node root) {
if (root != null) {
postorderRec(root.left);
postorderRec(root.right);
System.out.print(root.key + " ");
}
}
}
// Driver Class
public class Main{
// Main Function
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
// Inserting elements
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal:");
tree.inorder();
// Deleting elements
tree.delete(20);
tree.delete(30);
System.out.println("Inorder traversal after deletion:");
tree.inorder();
// Searching for an element
int searchKey = 70;
System.out.println("Is " + searchKey + " present in the tree? " + tree.search(searchKey));
// Traversals
System.out.println("Preorder traversal:");
tree.preorder();
System.out.println("Postorder traversal:");
tree.postorder();
}
}
Output:
Inorder traversal:
20 30 40 50 60 70 80
Inorder traversal after deletion:
40 50 60 70 80
Is 70 present in the tree? true
Preorder traversal:
50 40 70 60 80
Postorder traversal:
40 60 80 70 50
Complexity of the Above Method:
Operation | Explanation | Complexity |
|---|---|---|
Insertion Operation | To inserting the new key into the BST, we start from root and recursively traverse the tree until we find the appropriate position to insert the new key. Once we find a node where the new key belongs such as either as the left child or right side, we can insert the new node at the position while maintaining BST property. |
|
Deletion Operation | Delete a node involve from the BST involved three cases:
|
|
Searching Operation | Searching in the BST is done by the starting at root and comparing the target key with current node’s key. If the target key equal to current node’s key, we have found key. If the target is less than current node’s key, we have to left subtree, if is is greater we can move to the right subtree. This process is continue recursively until we found the key or reach the null node. |
|
Traversal Operations (Inorder, Preorder, Postorder) |
|
|
Java Program to Construct a Binary Search Tree
Binary Search Tree (BST) is the widely used data structure in computer science, primarily known for the efficient search, insertion, and deletion operations. It is the type of binary tree where each node has at most two children, referred to as the left child and the right child. Binary Search Tree offers the efficient average-case time complexity for operations such as search, insert, and delete operations is (O(log n)), it makes it suitable for applications requiring fast searching and
In this article, we will learn about Binary Search Tree.