class Node {
int data;
Node left;
Node right;
public Node(int value) {
data = value;
left = right = null;
}
}
public class BinarySearchTree {
Node root;
BinarySearchTree() {
root = null;
}
Node search(int key) {
return search(root,key);
}
Node search(Node root, int key) {
if(root == null) {
return null;
}
if(root.data == key) {
return root;
}
else if(root.data < key) {
return search(root.right, key);
}
else {
return search(root.left, key);
}
}
void insert(int key) {
root = insert(root, key);
}
Node insert(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.data)
root.left = insert(root.left, key);
else if (key > root.data)
root.right = insert(root.right, key);
return root;
}
void inOrder() {
inOrder(root);
}
void inOrder(Node root) {
if (root != null) {
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}
}
void delete(int key) {
root = delete(root, key);
}
Node delete(Node root, int key) {
if (root == null)
return root;
if (key < root.data)
root.left = delete(root.left, key);
else if (key > root.data)
root.right = delete(root.right, key);
else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.data = minValue(root.right);
root.right = delete(root.right, root.data);
}
return root;
}
int minValue(Node root) {
int min = root.data;
while (root.left != null) {
min = root.left.data;
root = root.left;
}
return min;
}
public static void main(String[] args) {
BinarySearchTree binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(16);
binarySearchTree.insert(10);
binarySearchTree.insert(25);
binarySearchTree.insert(13);
binarySearchTree.insert(18);
System.out.println("Inorder traversal: ");
binarySearchTree.inOrder();
Node searchedRes = binarySearchTree.search(5);
if (searchedRes == null) {
System.out.println("\n\nThe number 5 is not present in the BST");
}
else {
System.out.println("\n"+searchedRes.data+" is present in the BST");
}
System.out.println("\nLet us delete the element 10 from the Binary Search Tree");
binarySearchTree.delete(10);
System.out.println("\nInorder traversal after Deletion ");
binarySearchTree.inOrder();
binarySearchTree.insert(3);
System.out.println("\nInorder traversal after insertion of the new element 3 : ");
binarySearchTree.inOrder();
}
}
So, we would be constructing the below Binary Search Tree :
And we have the below methods :
Firstly, we would be constructing the above Binary Search Tree, with the help of insert method..
binarySearchTree.insert(16);
So, we pass the element '16' to the 'insert(...)' method.
And the below 'insert(...)' method with one argument is called.
void insert(int key) {
root = insert(root, key);
}Initially, the variable 'root' is 'null' as defined the constructor. Then we take the key i.e. 16 in this case. And pass the 'root' and 'key' to the insert method with two arguments.
Node insert(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.data)
root.left = insert(root.left, key);
else if (key > root.data)
root.right = insert(root.right, key);
return root;
} The first line checks if the 'root' is null or not.
if (root == null) {
root = new Node(key);
return root;
}And in this case 'root' is null. So, we create a new Node object with the key i.e. 16.
Then assign it to the 'Node' object 'root'.
And return the Node 'root'.
return root;
In the next line we try to insert the element 10 in the Binary Search Tree using the 'insert(...)' method.
binarySearchTree.insert(10);
And the 'insert(...)' method is called.
And in the similar way we check,
if (key < root.data)
root.left = insert(root.left, key);
else if (key > root.data)
root.right = insert(root.right, key);If the 'key' i.e. 10 is less than the root element 'root.data'. The first condition matches.
if (key < root.data)
root.left = insert(root.left, key); And a recursive call is made to 'insert(...)' method.
root.left = insert(root.left, key);
So, the method executes and returns the Node that contains '10', setting the value of 'root.left' with this Node that contains '10'.
Similarly, all the elements are inserted using the 'insert(...)' method.
binarySearchTree.insert(25); binarySearchTree.insert(13); binarySearchTree.insert(18);
And the below Binary Search Tree is formed,
Then we use the 'inOrder()' method to traverse the Binary Search Tree.
binarySearchTree.inOrder();
Next, we search, if the element '5' is present in the Binary Search Tree using the 'search(...)'method.
Node searchedRes = binarySearchTree.search(5);
And the 'search(...)' method with one argument is called.
Node search(int key) {
return search(root,key);
}And the 'search(...)' method with two arguments is called with the 'key' element as 5(i.e The element to be searched).
Node search(Node root, int key) {
if(root == null) {
return null;
}
if(root.data == key) {
return root;
}
else if(root.data < key) {
return search(root.right, key);
}
else {
return search(root.left, key);
}
} So, there are a couple of 'if' statements, where the first 'if' statement checks if the root element is null or not.
if(root == null) {
return null;
}In this case the root element is '16'. So, we go to the next 'if' statement that checks if the 'key' element 5 (i.e. The element to be searched), is equal to the root element or not.
if(root.data == key) {
return root;
}In this case the root element is 16 which is not equal to the element that needs to be searched.
So, the next'if' statement checks, 'if' the element that needs to be searched(i.e. 5) is greater than the root element(i.e. 16) or not.
else if(root.data < key) {
return search(root.right, key);
}In this case '5' is less than '16'. So, even this condition is not satisfied.
The logic behind this 'if' statement is to check, if the element to be searched is greater than the root element or not. If the element to be searched, is greater than the root element then it should be on the right side of the tree and we are suppose to search there.
Now, since '5' is less than '16'. We come to the final else statement. Which assumes that the element to be searched (i.e. 5) is less than the root element (i.e. 16) and must be on the left hand side.
else {
return search(root.left, key);
}Now, in this else statement, a recursive call is made to the 'search(root.left, key)' method. So, the assumption is that the element '5' should be in the Left Sub-Tree.
And the 'Node search(Node root, int key)' method is called again with the 'root' as 10.
The same way all the if statements are executed and finally, the element '5' is not found in the Binary Search Tree.
Next, we try to delete the element '10' from the Binary Search Tree.
binarySearchTree.delete(10);
Calling the 'delete(...)' method.
Similarly, in this case, 'delete(...)' method with one argument is called,
void delete(int key) {
root = delete(root, key);
}And the 'delete(...)' method with two arguments is called.
Node delete(Node root, int key) {
if (root == null)
return root;
if (key < root.data)
root.left = delete(root.left, key);
else if (key > root.data)
root.right = delete(root.right, key);
else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.data = minValue(root.right);
root.right = delete(root.right, root.data);
}
return root;
} So, we are trying to delete the element '10' from the Binary Search Tree. So, the 'key' is 10 that we have passed to the 'delete(...)' method.
The 'delete(...)' method is almost same as the 'search(...)' method.
In the 'search(...)' method, we have located the element to be searched. Even in 'delete(...)' method, we will locate the element first(The code is exactly same as the search(...) method). Then call the 'minValue(root.right)' method
The 'minValue(...)' method will find the inorder-successor. i.e. When we delete the element, we need to find a replacement of it, so that the Binary Search Tree properties should be intact.
Thus, we go to the Right Sub-Tree of the element to be deleted. And as we know the Right Sub-Tree contains all the elements that are greater than the root element. So, we have to find the smallest element from the Right Sub-Tree..
And, as we know the smallest element of the Right Sub-Tree resides on the leftmost leaf.
And that's exactly what we will find in 'int minValue(Node root)' method.
int minValue(Node root) {
int min = root.data;
while (root.left != null) {
min = root.left.data;
root = root.left;
}
return min;
}