Binary Search Tree Implementation in Java by Trilochan Tarai
A Binary Search Tree (BST) is a specialized type of binary tree that follows these specific rules:
Binary Property: Each node can have at most two children, often referred to as the left child and the right child.
Search Property:
Uniqueness: The values in the BST are usually unique, though variations exist that allow duplicate values.
//Binary Search Tree Implementation in Java:
class BinarySearchTree
{
class Node
{
int key;
Node left, right;
Node(int key)
{
this.key=key;
left=null;
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)
{
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);
}
}
//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+"->");
}
}
void deleteKey(int key)
{
root=deleteRec(root,key);
}
Node deleteRec(Node root, int key)
{
if(root==null)
{
Recommended by LinkedIn
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 inordersuccessor in position of the node to be deleted
root.key=minValue(root.right);
//Delete the inorder succesor
// The key to delete in the right subtree is the value that was just copied to root.key
root.right=deleteRec(root.right, root.key); // Corrected line
}
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;
}
//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);
}
// If none of the above conditions are met, it means root.key > key
// So, we search in the left subtree.
return searchRec(root.left, key);
}
public static void main(String[] args)
{
BinarySearchTree obj=new BinarySearchTree();
obj.insert(7);
obj.insert(3);
obj.insert(1);
obj.insert(5);
obj.insert(4);
obj.insert(10);
obj.insert(15);
obj.insert(13);
System.out.println("Inorder Traversal:");
obj.inorder();
System.out.println("\n\nAfter deleting 10");
obj.deleteKey(10);
obj.inorder();
System.out.println("\n");
int searchKey=15;
System.out.println("is"+searchKey+"present in tree?"+obj.search(searchKey));
System.out.println("Preorder Traversal:");
obj.preorder();
System.out.print("Postorder Traversal:");
obj.postorder();
}
}
Output:
Inorder Traversal:
1->3->4->5->7->10->13->15->
After deleting 10
1->3->4->5->7->13->15->
is15present in tree?true
Preorder Traversal:
7->3->1->5->4->15->13->
Postorder Traversal:1->4->5->3->13->15->7->
Absolutely fantastic, the basics of DSA which every IT enthusiasts should be aware about.