Implementing a Binary Search Tree in Java
A Binary Search Tree is a non-linear data structure composed of nodes and links. It is a type of binary tree which means that each node can have a maximum of two children.
A binary search tree must also follow the given two conditions.
- The left node's value should be less than its parent node's value.
- The right node's value should be greater than its parent node's value.
The above two conditions must be true for all nodes of the tree. The following image shows a binary search tree.
The general structure of the node of a binary tree is shown below. It consists of a value and two pointers - one to its left child and the other to its right child.
The node class of a binary search tree is shown below.
class BSTNode
{
int value;
BSTNode leftChild;
BSTNode rightChild;
BSTNode(int val)
{
this.value = val;
this.leftChild = null;
this.rightChild = null;
}
}
A binary search tree can have four basic operations - Insertion, Deletion, Searching, and Traversing. Let's learn how to implement a binary search tree in Java.
Insertion in Binary Search Tree
Inserting an element in a binary search tree is pretty straightforward. We just need to find its correct position by using the following algorithm. This is done to ensure that the tree after insertion follows the two necessary conditions of a binary search tree.
- If the new value is less than the current node value, then recurse to the left child.
- If the new value is greater than the current node value, then recurse to its right child.
- If the current node is Null, then add the new value at this position.
public static BSTNode insert(int value, BSTNode current)
{
if(current == null)
{
BSTNode newNode = new BSTNode(value);
return newNode;
}
else
{
if(value < current.value)
current.leftChild = insert(value, current.leftChild);
else
current.rightChild = insert(value, current.rightChild);
}
return current;
}
For example, let's try to insert the value 6 into the following tree.
We first compare 6 with the root value, 12. 6 is smaller than 12 so we will move to the left subtree and compare 6 to the root of the left subtree. 6 is smaller than 7 so we will again move to the left subtree. Now, 6 is greater than 5 so we move to the right subtree. But the right subtree is null or does not exist, so the new node will be added at this position.
Searching in Binary Search Tree
Searching a value in a binary search tree follows pretty much the same logic that we discussed for the insertion of an element. The only difference is that if at any moment the current node is Null, then it indicates that the value is not present in the tree. Instead of inserting the value, we will just return False.
- If the current node's value matches the value that we are trying to find, then return True.
- If the current node's value is greater than the value that we are trying to find, then recurse to the left child.
- If the current node's value is smaller than the value that we are trying to find, then recurse to the right child.
- If the current node is Null then return False.
The code for this method is shown below.
public static boolean search(int key, BSTNode current)
{
if(current == null)
return false;
if(current.value == key)
return true;
else
{
if(key < current.value)
return search(key, current.leftChild);
else
return search(key, current.rightChild);
}
}
Deletion in Binary Search Tree
The process of deleting a node from a binary search tree is a bit more complex than insertions and searching. First, we need to find the node that we want to delete. The logic for this part will be the same as discussed in insertion and searching.
After finding the correct node, we need to follow one of the below steps according to the nature of the node.
- If it is a leaf node(a node with no children) then we can simply replace that node with null.
- If the node has a single child then it is deleted and the child takes its position.
- If the node has two children then it is deleted and either the maximum node from its left subtree takes its position, or the minimum value from its right subtree takes its position. For our code, we will use the smallest value from the right subtree.
public static BSTNode delete(int value, BSTNode current)
{
if(current == null)
return current;
if(value < current.value)
current.leftChild = delete(value, current.leftChild);
else if(value > current.value)
current.rightChild = delete(value, current.rightChild);
else if(value == current.value)
{
if(current.leftChild != null && current.rightChild != null)
{
int min = current.rightChild.value;
BSTNode temp = current.rightChild;
while(temp.leftChild != null)
{
min = temp.leftChild.value;
temp = temp.leftChild;
}
current.value = min;
current.rightChild = delete(min, current.rightChild);
}
else if(current.leftChild == null)
return current.rightChild;
else if(current.rightChild == null)
return current.leftChild;
else
return null;
}
return current;
}
For example, let's try to delete 12, 20, and 9 from the following tree.
Deleting 12 from the Binary Search Tree
Deleting 20 from Binary Search Tree:
Deleting 9 from Binary Search Tree:
Traversing in Binary Search Tree
We can traverse a binary search tree in two different ways. Let's learn these two techniques.
Depth-First Search
As the name suggests, in depth-first search we will explore one particular node as far as possible before moving on to the next node. It has three variations that depend on the order in which we explore the root, the left child, and the right child.
Preorder: If we first visit the root node, then the left child, and finally the right child, then this method of traversing is called preorder traversal.
public static void preorder(BSTNode current)
{
if(current == null)
return;
else
{
System.out.print(current.value + " ");
preorder(current.leftChild);
preorder(current.rightChild);
}
}
Postorder: If we first explore the left child, then the right child, and finally visit the root node, then this method of traversing is called postorder traversal.
public static void postorder(BSTNode current)
{
if(current == null)
return;
else
{
postorder(current.leftChild);
postorder(current.rightChild);
System.out.print(current.value + " ");
}
}
Inorder: If we first explore the left child, then visit the root node, and finally the right child, then this method of traversing is called inorder traversal. For binary search trees, the inorder traversal will return the values in sorted order. This happens because the left child is smaller than the root and the root itself is smaller than the right child.
public static void inorder(BSTNode current)
{
if(current == null)
return;
else
{
inorder(current.leftChild);
System.out.print(current.value + " ");
inorder(current.rightChild);
}
}
Breadth-First Search
Breadth-first search traverses a tree level by level. It will first print all the values present in one level before moving on to the next. It is also known as the level order traversal. The following image shows the different levels of a binary tree. The level order traversal of the following tree will be - 12 7 20 5 9 21.
The iterative breadth-first search implementation is shown below. A queue is used to store the nodes.
public void static levelOrder(BSTNode current)
{
if(current == null)
return;
Queue<BSTNode> q = new LinkedList<BSTNode>();
q.add(current);
while(q.isEmpty() == false)
{
BSTNode temp = q.remove();
System.out.print(temp.value + " ");
if(temp.leftChild != null)
q.add(temp.leftChild);
if(temp.rightChild != null)
q.add(temp.rightChild);
}
}
Practical Demonstration
Let's look at a practical demonstration of all of the above methods.
First, let's create the binary tree that we have shown in the above images.
public static void main(String args[])
{
//constructing the tree
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
}
Now, let's use the search method to search for some existing and non-existing values.
public static void main(String args[])
{
//constructing the tree
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
//searching
System.out.println(search(7, root));
System.out.println(search(9, root));
System.out.println(search(17, root));
}
true
true
false
Let's print the entire tree by using different traversal techniques.
public static void main(String args[])
{
//constructing the tree
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
//Traversals
System.out.print("\nPreorder Traversal: ");
preorder(root);
System.out.print("\nPostorder Traversal: ");
postorder(root);
System.out.print("\nInorder Traversal: ");
inorder(root);
System.out.print("\nLevel Order Traversal: ");
levelOrder(root);
}
Preorder Traversal: 12 7 5 9 20 21
Postorder Traversal: 5 9 7 21 20 12
Inorder Traversal: 5 7 9 12 20 21
Level Order Traversal: 12 7 20 5 9 21
Let's delete a few nodes and print the traversals.
public static void main(String args[])
{
//constructing the tree
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
//Deleting nodes
root = delete(12, root);
root = delete(9, root);
//Traversals
System.out.println("\n\nAfter deletion");
System.out.print("\nPreorder Traversal: ");
preorder(root);
System.out.print("\nPostorder Traversal: ");
postorder(root);
System.out.print("\nInorder Traversal: ");
inorder(root);
System.out.print("\nLevel Order Traversal: ");
levelOrder(root);
}
After deletion
Preorder Traversal: 20 7 5 21
Postorder Traversal: 5 7 21 20
Inorder Traversal: 5 7 20 21
Level Order Traversal: 20 7 21 5
Frequently Asked Questions
Q. What is the difference between Binary Tree and Binary Search Tree?
A Binary Tree and a Binary Search Tree both can have a maximum of two children for a particular node. In a binary search tree, the left child should be smaller than the root and the right child should be greater than the root, and this condition should be true for all nodes. The binary tree does not have any such conditions on the left and right children.
Q. Does Binary Search Tree use the Binary Search Algorithm for searching an element in the tree?
The searching algorithm of a binary search tree works on the same principle as the binary search algortihm. In every iteration, we are narrowing our search down to just half of the tree. This leads to the average time complexity of O(log(n)).
Q. What are some real-world use cases of a Binary Search Tree?
Binary search trees are very commonly used in 3-D game engines to render and spawn objects. Compilers also use binary search trees to parse syntax expressions efficiently.
Summary
A binary search tree is a variation of normal binary trees. In this tutorial, we learned how to perform insert and delete elements in a binary search tree. We also learned how to search for an element and how to traverse the entire tree using the breadth-first and depth-first approaches. I hope you found this tutorial helpful and learned something new.
