Trees are one of the most significant data structures in Java. There are various types of trees offered in Java but we will be specifically focusing on Binary search trees.
In this article, we will be discussing the working of a binary search tree in Java. Along with that, we will also explore some crucial operations performed on a binary search tree.
Keywords to Know
If you have studied trees before, these terminologies must have come across you. These terms are very important to understand first before diving into the concepts and functionalities of a binary search tree in Java.
Node: It is a unit that the tree is made up of. Each node contains a piece of data and a pointer to other nodes in the tree.
Children: A successor node in the tree. Except for leaves (last nodes), every node in a binary tree can have a maximum of two children.
Parent: A predecessor node in the tree. Every node has a parent, except the root node.
Root: A root is the starting node in a tree. It does not have a parent as it is the first node in the tree.
Leaves: These are the last nodes in a tree, making them the end terminals of the tree. Hence, leaves do not have any children.
Binary Search Tree in Java
A binary tree is a specific type of tree where each node, excluding the leaves, has two children. A binary search tree extends this concept of a binary tree by fulfilling the following conditions,
- Every left node must have a smaller value than its parent node
- Every right node must have a bigger value than its parent node
This is made sure at the time of insertion of data in the nodes. These properties might seem trivial but they proved to be very helpful in solving various algorithmic problems. On top of that, a Binary search tree in Java also supports all the tasks done using a simple binary tree while taking significantly lesser time.
Implementation of a Binary Search Tree in Java:
For implementing a Binary Search Tree in Java, first of all, you need to create a Node class that stores the data to be saved in the nodes along with right and left variables of Node type to keep a reference of each child.
See Code:
Static class Node {
Public int data;
Public Node left;
Public Node right;
Public Node(int data) {
this.data = data;
this.right = null;
this.left = null;
}
}
After that you can start adding nodes to your binary search tree, The first Node is usually called the root to make the code easier to understand:
public class BinarySearchTree {
Node root;
public BinarySearchTree() {
this.root = null;
}Inserting into a Binary Search Tree in Java:
The Insertion process requires a method that creates a new node and inserts it in the tree at the right position depending on the data to be inserted.
As per the rule, if the value to be inserted is less than the parent node, a left child node is created whereas if the value is greater than a right child will be created. Lastly, the value will be added to the newly created node.
This scenario is for when we just have a root in a tree but if we already have some level in a binary search tree. The following steps are performed to traverse through the tree till the last node (leave) where the new node will be inserted.
- Starting with the root, If the value to be inserted is greater than the existing root, move down a level through the right pointer of the root.
- If the value to be inserted is lesser than the existing root, move down a level through the left pointer of the root.
- Keep repeating this process for all nodes till you reach the leaves.
The following code demonstrates the above-explained process in Java:
public Node root;
public BinarySearchTree() {
this.root = null;
}
// insert method
public void insertData(int newData) {
this.root = insert(root, newData);
}
public Node insertData (Node root, int newData) {
// Case 1: when root is null
if (root == null) {
// Insert new data, if root is null.
root = new Node(newData)
return root;
}
// Checking whether the root data is same or equal to newData
else if (root.data >= newData) {
// if root data is greater than the new data then go to the left sub-tree
root.left = insert(root.left, newData);
} else {
// if current root data is less than the new data then go to the right sub-tree
root.right = insert(root.right, newData);
}
return root;
}
//Traversing the tree
public void preorder() {
preorder(root);
}
public void preorder(Node root) {
if (root == null) {
return;
}
System.out.print(root.data + ", ");
preorder(root.left);
preorder(root.right);
}
public static void main(String[] args) {
BinarySearchTree obj1 = new BinarySearchTree();
// calling the the method insert
obj1.insertData(2);
obj1.insertData(8);
obj1.insertData(1);
obj1.insertData(4);
obj1.insertData(6);
obj1.preorder();
}
}Output Will be: 2 1 8 4 6
Deletion from a Binary Search Tree in Java
Deletion is a relatively complicated task than insertion, this is because deletion depends on the node that needs to be deleted. If the node to be deleted has no children (means, it is a leaf) then it can be easily removed from the tree. If a node has one child, after deleting that node the child has to be moved up to replace the deleted node.
It gets trickier when we have to delete a node with two children. First, we need to find the node with the smallest value in the right subtree. That will now replace the deleted node.
The following code is demonstrating all three scenarios for deleting a node when the node to be deleted has no child, 1 child or 2 children:
public void nodeDeletion(Node node)
{
nodeDeletion(this.root, node);
}
private Node nodeDeletion (Node root, Node node)
{
if (root == null)
{
return null;
}
else if (node.data < root.data)
{
// goes to left sub tree
root.left = nodeDeletion(root.left, node);
}
else if (node.data > root.data)
{
// goes to right sub tree
root.right = nodeDeletion(root.right, node);
}
else if(root.data==node.data){
// case 3: 2 children
if (root.left != null && root.right != null) {
int lmax = findMaxData(root.left);
root.data = lmax;
root.left = nodeDeletion(root.left, new Node(lmax));
return root;
}
//case 2: one child
else if (root.left != null) {
return root.left;
}
else if (root.right != null) {
return root.right;
}
//case 1: no child
else {
return null;
}
}
return root;
}
public static void main(String[] args)
// Implementing on the previously made object (obj1)
obj1.nodeDeletion (new Node(6));
obj.preorder();
}
}Output : 2 1 8 4
Search for an Element in a Binary Search Tree
The process of searching in a binary search tree is quite straightforward. To search for a value, three conditions are needed to be checked,
- Starting from the root, If the value is equal to the current node, then you just return the index of the current node.
- If the value is lesser than the current node, you will have to move to the node in the right subtree.
- If the value is greater than the current node, move to the left subtree.
These three steps will be repeated until the value is found. If the value is not found and you have reached the leaves, it will indicate that the value does not exist in the tree.
See Code:
public boolean searchData(int data) {
return search(this.root, data);
}
private boolean searchData(Node root, int data) {
if (root == null) {
return false;
} else if (root.data == data) {
return true;
} else if (root.data > data) {
return search(root.left, data);
}
return searchData(root.right, data);
}
//Traversing the tree
public void preorder() {
preorder(root);
System.out.println();
}
public void preorder(Node root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
public static void main(String[] args) {
// Applying on the previously made object, obj1
obj1.preorder();
System.out.println(obj1.search(1));
System.out.println(obj1.search(7));
}
}Output : 2 1 8 4 true false
Conclusion
A binary search tree in Java is an extremely useful data structure. This article explores various operations on a binary search tree along with their Java codes in java.
Also Read: A Guide to the Java ExecutorService
It should be adequate to bring you to pace with the basics of the binary search tree in Java and its practical uses.
