How to implement Binary Search tree in Java?

A binary search tree or BST is a popular data structure which is used to keep elements in order. A binary search tree is a binary tree where the value of a left child is less than or equal to the parent node and value of the right child is greater than or equal to the parent node.

                              Since its a binary tree, it can only have 0, 1 or two children. What makes a binary search tree special is its ability to reduce the time complexity of fundamental operations like add, remove and search, also known as insert, delete and find. In a BST, all these operations (insert, remove and find) can be performed in O(log(n)) time. The reason for this improvement in speed is because of the unique property of binary search tree, where for each node, the data in the left child is less than (or equal) and the data in the right child is greater than (or equal) to the data in said node.

In Programming interviews, you will see many data structure and algorithmic questions based upon binary search tree e.g. check if a binary tree is a BST or not? Or, write a program to check if BST is balanced or not. In order to solve that problem, you must know how to implement BST in Java.

In this tutorial, I will teach you how to implement a binary search tree in Java, which you can use to solve any binary search tree or binary tree based coding problems.

Binary Search tree in Java

Here, You will learn how to create a binary search tree with integer nodes. I am not using Generics just to keep the code simple but if you like you can extend the problem to use Generics, which will allow you to create a Binary tree of String, Integer, Float or Double. Remember, you make sure that node of BST must implement the Comparable interface. This is what many Java programmer forget when they try to implement binary search tree with Generics.

Here is an implementation of a binary search tree in Java. It's just a structure, we will subsequently add methods to add a node in a binary search tree, delete a node from binary search tree and find a node from BST in the subsequent part of this binary search tree tutorial.

In this implementation, I have created a Node class, which is similar to our linked list node class, which we created when I have shown you how to implement linked list in Java. It has a data element, an integer and a Node reference to point to another node in the binary tree.

I have also created four basic functions, as shown below:

•  getRoot(), returns the root of binary tree
•  isEmpty(), to check if binary search tree is empty or not
•  size(), to find the total number of nodes in a BST
•  clear(), to clear the BST

That's all in this tutorial about how to implement binary search tree in Java. In this tutorial, you have learned to create the structure of BST using Node class and some basic function. In next couple of tutorials, you will learn some more interesting things with BST e.g. writing a method to add Nodes in BST, this method must make sure that property of binary search tree is not violated. I mean, it first needs to find a right place and then needs to add the element. Subsequently, you will also learn how to search a node in binary search tree.

Writing unit test is one of the best programming practice along with code review. It's natural and I had experienced it myself that unit test, not only provides code coverage, but also present unique opportunities for code refactoring. Many times, while writing unit tests, I have discovered better names for my methods and refactored large methods into smaller ones. JUnit tests also helps to organize code and evaluate encapsulation.

                                         There is a good chance of you discovering that a particular field or method is exposing implementation detail, and should be abstracted in public method. What all this means is, you, a Java developer, must write unit tests. Since it always helps to start smaller, this JUnit tutorial will present another simple JUnit example to show how to write unit test in Java. In this JUnit tutorial, we will implement a linked list in Java and we will write unit test cases for a linked list. For those, who are not familiar with the linked list, it's one of the fundamental data structure to store objects, like an array, which is also used to store object. By the way, there is much difference between linked list and array data structure, which is subject of another blog post, but the main difference is in the way objects are stored. An array needs contiguous memory, while linked list doesn't need that.