In this article, we will take a deeper look at the binary search tree in Java.We will see how to implement the binary search tree in Java and what are its different characteristics.
1. What is Binary Tree
Before we get in the details of the binary search tree in Java and how to implement it, it’s very important that we clearly understand what is a binary tree and what are its different characteristics. This will help us when we will implement the binary tree in Java. A binary tree is a non-linear data structure where data objects are generally organized in terms of hierarchical relationship. A binary tree is a tree where every node has 2 for fewer children. We call these nodes as left and right child of the binary tree. Here is how a binary tree may look like:
In binary tree, every node contains the following part:
- Data (actual data)
- pointer to left child.
- pointer to right child.
This is how a typical node will look like in Java
public class Node{
private int data;
private Node left;
private Node right;
public Node(int data){
this.data= data;
}
}Read binary tree data structure to get more understanding about binary tree data structure
2. What is Binary Search Tree
This is a very common question “What is Binary Search tree?“. To put it simply, a binary search tree is a binary tree with the following properties.
- Left child is always less than the parent.
- Right child is always greater than the parent.
- The left and right sub-tree each must be a binary search tree.
The binary search tree allows a faster search and deletion of items from the tree. Binary search tree also known as ordered or sorted binary tree. This is how a BST may look like with the data elements.
There are different opinion as how to store the duplicate values in the binary search tree. Some implementation does not allow duplicate values, while others store it on right or left sub-tree. We purely based this decision on the application type.
Binary search tree is one of the fundamental data structure and used to create more abstract data structure like:
- Sets.
- Multisets.
- Associative arrays
3. Binary Search Tree in Java
We will implement a binary search tree in Java. A binary search tree provided the following common operations, and we will implement all these operations.
- Inserting Elements.
- Search Element in binary search tree.
- Delete elements from BST.
- Tree Traversal
- Depth-First Search
- Breadth-First Search
This article aim to provide you understanding of the BST data structure.If you are looking for using the Tree in your production code, consider using TreeMap or similar implementation from JDK. Before we get in to details, Let’s define few basic structures for our binary search tree in Java.
3.1 Binary Search Tree Node
Every node in our binary tree can contain the following information.If you like, you can also define node class as inner class for the Binary search tree class
- Actual data (int in our case).
- Reference to the left child.
- Reference to the right child.
public class Node {
private int data;
private Node left;
private Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}3.2 Binary Search Tree Class
Next is the Binary search tree class. This class will have the different methods to perform various operations (e.g. insert, delete, search etc.). Here is a high-level overview of the class:
public class BinarySearchTree{
private Node root;
//methods for binary search tree
}Now we have the basic understanding of the Binary search tree and its structure, let’s see how to implement binary search tree in Java. We will start adding a node to the binary search tree.
4. Insert Element to Binary Search Tree
Keep in mind the core property of the binary search tree while you insert the key in the tree. The first step is to find the place where we want to insert the key in the binary tree.Also keep in mind that a new node will always be inserted at the leaf. So inserting the node in the binary search tree is a 2-step process – Search + Insert, here is the high level workflow for the insert method.
- Start from the root node.
- If the new node value is lower than the current node, we go to the left child of the current node.
- If the value is greater than the current node, go to the right child.
- Repeat the step
#2and#3, until the current node is null (leaf node). Insert the node in this position.
We can do most of the operation in BST using loop or through recursion. We will use the recursion for the code, but the same concept can be used if you want to iteration logic.
Let’s assume that we want to add 2 to our binary search tree (see the example in section 2). This is how the operation will look like:
Let’s see how the insert code looks like and then we will talk about the insert logic.
public class BinarySearchTree {
private Node root;
/**
* Our main insert method which takes the integer as input and will pass
* the parameter to internal insert method with the root node;
* @param data
* @return boolean status.
*/
public boolean insert(int data) {
root = insert(root, data);
return true;
}
private Node insert(Node node, int data) {
/**
* If Node is null, either tree is empty or this is the
* leaf node and we can create the node and return the new node.
*/
if (node == null) {
return new Node(data);
}
/**
* if data is less than the current element,
* let's go to the left side of the tree. We are giving a recursive call to the insert method
* and will wait until response is back.
*/
if (node.data > data) {
node.left = insert(node.left, data);
}
/**
* If data is greater than the current element,
* let's go the right side of the tree.We are giving a recursive call to the insert method
* and will wait until response is back. Other option is to use while loop.
*/
if (node.data < data) {
node.right = insert(node.right, data);
}
/**
* Element already exist is the tree. Please note there are multiple variations for this step.
* Few implementation do not allow duplicate element in BST (we are using same approach).
* while other allow duplicate in BST and they can go either to left or right of the tree.
*/
else{
return node;
}
return node;
}
}So the public boolean insert(int data) is the taking user input and we are passing this input to an internal method private Node insert(Node node, int data) with a root node. The root node will help us traverse tree recursively until we get the position where we want to insert the node in the tree. Based on the value in the node and input passed by the user, we are moving to either left or right of our tree. Finally, let’s see how to insert tree nodes.
public class BinarySearchTreeTest {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
/* We are building a BST as below
52
/ \
15 56
/ \ / \
9 11 54 61
/ \
3 5 */
bst.insert(52);
bst.insert(15);
bst.insert(56);
bst.insert(9);
bst.insert(11);
bst.insert(54);
bst.insert(3);
bst.insert(5);
bst.insert(61);
}
}5. Binary Search Tree Time Complexity
Binary tree is an efficient algorithm. Here is the time complexity for the BST.
- The best case time complexity for BST is
O(log(n)). - The worst case time complexity for BST is
O(h)where h is the height of the binary search tree.
The worst case can happen when we have an unbalanced binary tree. Here, we have to travel from root node to the deepest leaf node before inserting the element. Look at the following image for better clarity and think about adding 5 in the tree. We need to go all the way to the leaf node before we insert the Node (which is equal to the height of the tree).
We can achieve the constant O(log(n)) time complexity for BST in all cases using self balancing tree like AVL or Red-Black Binary tree.
Summary
In this article, we started with the basic of Binary search tree and how to implement binary search tree in Java. I am keeping this article short and will covert the search and deletion in the next lesson. The source code for this series is available on the GitHub.
