Most of the students fresh out of their engineering studies or those who are still studying will have the concept of **Binary Search Trees** fresh in their minds. But with most of the people who have been out of college for many years now will kind of be having a not so clear idea of Binary Search trees unless they have been using it or related concepts at their work. Also you can read the extensive concepts about this topic on any of the popular data structure book in the store.

books:

**In this tutorial I would show how to implement a Binary Search Tree (BST) in Java and also show the following operations:**

**Inserting/Building a BST****Finding maximum value node in BST****Finding minimum value node in BST****Inorder Traversal of BST****Preorder Traversal of BST****Postorder Traversal of BST**

## What is a Binary Search Tree (BST)?

**Binary Search Tree (BST) is a binary tree data structure with a special feature where in the value store at each node is greater than or equal to the value stored at its left sub child and lesser than the value stored at its right sub child**. Lets look at an example of a BST:

In the above example you can see that at each node the value in the left child is lesser than or equal to the value in the node and the value in the right child is greater than the value in the node.

## Building a Binary Search Tree (BST)

Now that we have seen how a BST looks, let me show you how one can build a BST and insert nodes into the tree by implementing the algorithm in Java. **The basic idea is that at each node we compare with the value being inserted. If the value is lesser then we traverse through the left sub tree and if the value is greater we traverse through the right subtree.** Suppose we have to insert the value **64** in the above BST, lets look at the nodes traversed before its inserted at the right place:

Each node in the BST is represented by the below java class:

public class Node<T> { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } }

Lets look at the code in Java for achieving the above logic:

public class BinarySearchTree { public Node root; public void insert(int value){ Node node = new Node<>(value); if ( root == null ) { root = node; return; } insertRec(root, node); } private void insertRec(Node latestRoot, Node node){ if ( latestRoot.value > node.value){ if ( latestRoot.left == null ){ latestRoot.left = node; return; } else{ insertRec(latestRoot.left, node); } } else{ if (latestRoot.right == null){ latestRoot.right = node; return; } else{ insertRec(latestRoot.right, node); } } } }

## Finding Maximum and Minimum Value in BST

If you have noticed in the above example that the leftmost node has the lowest value and the rightmost node has the highest value. This is due to the sorted nature of the tree.

Using this principle the below methods return us the lowest and highest value in the Binary Search Tree:

/** * Returns the minimum value in the Binary Search Tree. */ public int findMinimum(){ if ( root == null ){ return 0; } Node currNode = root; while(currNode.left != null){ currNode = currNode.left; } return currNode.value; } /** * Returns the maximum value in the Binary Search Tree */ public int findMaximum(){ if ( root == null){ return 0; } Node currNode = root; while(currNode.right != null){ currNode = currNode.right; } return currNode.value; }

## Traversing the Binary Search Tree (BST)

Traversing the tree or BST in this case is visiting each of the nodes present in the tree and performing some operation with the value present in the node which in this case will be printing the value present in the node. **When we traverse the tree we have to visit the value present in the node, then node’s right sub tree and the left sub tree**. Visiting the right and left sub tree will be a recursive operation. The order in which we perform the three operations i.e visiting the value, right sub tree and left sub tree gives rise to three traversal techniques:

**Inorder Traversal****Preorder Traversal****Postorder Traversal**

### Inorder Traversal

In this traversal the left sub tree of the given node is visited first, then the value at the given node is printed and then the right sub tree of the given node is visited. This process is applied recursively all the node in the tree until either the left sub tree is empty or the right sub tree is empty.

Applying the Inorder traversal for the give example we get: 3, 10, 17, 25, 30, 32, 38, 40, 50, 78, 78, 93.

/** * Printing the contents of the tree in an inorder way. */ public void printInorder(){ printInOrderRec(root); System.out.println(""); } /** * Helper method to recursively print the contents in an inorder way */ private void printInOrderRec(Node currRoot){ if ( currRoot == null ){ return; } printInOrderRec(currRoot.left); System.out.print(currRoot.value+", "); printInOrderRec(currRoot.right); }

### Preorder traversal

In this traversal the value at the given node is printed first and then the left sub tree of the given node is visited and then the right sub tree of the given node is visited. This process is applied recursively all the node in the tree until either the left sub tree is empty or the right sub tree is empty.

Applying the Preorder traversal for the give example we get: 40, 25, 10, 3, 17, 32, 30, 38, 78, 50, 78, 93.

/** * Printing the contents of the tree in a Preorder way. */ public void printPreorder() { printPreOrderRec(root); System.out.println(""); } /** * Helper method to recursively print the contents in a Preorder way */ private void printPreOrderRec(Node currRoot) { if (currRoot == null) { return; } System.out.print(currRoot.value + ", "); printPreOrderRec(currRoot.left); printPreOrderRec(currRoot.right); }

### Postorder Traversal

In this traversal the left sub tree of the given node is traversed first, then the right sub tree of the given node is traversed and then the value at the given node is printed. This process is applied recursively all the node in the tree until either the left sub tree is empty or the right sub tree is empty.

Applying the Postorder traversal for the give example we get: 3, 17, 10, 30, 38, 32, 25, 50, 93, 78, 78, 40.

/** * Printing the contents of the tree in a Postorder way. */ public void printPostorder() { printPostOrderRec(root); System.out.println(""); } /** * Helper method to recursively print the contents in a Postorder way */ private void printPostOrderRec(Node currRoot) { if (currRoot == null) { return; } printPostOrderRec(currRoot.left); printPostOrderRec(currRoot.right); System.out.print(currRoot.value + ", "); }

The complete code which builds the tree for the example explained in this code and prints the maximum, minimum value, inorder traversal, preorder traversal and post order traversal can be found below:

/** * Represents a node in the Binary Search Tree. */ public class Node<T> { //The value present in the node. public int value; //The reference to the left subtree. public Node left; //The reference to the right subtree. public Node right; public Node(int value) { this.value = value; } } /** * Represents the Binary Search Tree. */ public class BinarySearchTree { //Refrence for the root of the tree. public Node root; public BinarySearchTree insert(int value) { Node node = new Node<>(value); if (root == null) { root = node; return this; } insertRec(root, node); return this; } private void insertRec(Node latestRoot, Node node) { if (latestRoot.value > node.value) { if (latestRoot.left == null) { latestRoot.left = node; return; } else { insertRec(latestRoot.left, node); } } else { if (latestRoot.right == null) { latestRoot.right = node; return; } else { insertRec(latestRoot.right, node); } } } /** * Returns the minimum value in the Binary Search Tree. */ public int findMinimum() { if (root == null) { return 0; } Node currNode = root; while (currNode.left != null) { currNode = currNode.left; } return currNode.value; } /** * Returns the maximum value in the Binary Search Tree */ public int findMaximum() { if (root == null) { return 0; } Node currNode = root; while (currNode.right != null) { currNode = currNode.right; } return currNode.value; } /** * Printing the contents of the tree in an inorder way. */ public void printInorder() { printInOrderRec(root); System.out.println(""); } /** * Helper method to recursively print the contents in an inorder way */ private void printInOrderRec(Node currRoot) { if (currRoot == null) { return; } printInOrderRec(currRoot.left); System.out.print(currRoot.value + ", "); printInOrderRec(currRoot.right); } /** * Printing the contents of the tree in a Preorder way. */ public void printPreorder() { printPreOrderRec(root); System.out.println(""); } /** * Helper method to recursively print the contents in a Preorder way */ private void printPreOrderRec(Node currRoot) { if (currRoot == null) { return; } System.out.print(currRoot.value + ", "); printPreOrderRec(currRoot.left); printPreOrderRec(currRoot.right); } /** * Printing the contents of the tree in a Postorder way. */ public void printPostorder() { printPostOrderRec(root); System.out.println(""); } /** * Helper method to recursively print the contents in a Postorder way */ private void printPostOrderRec(Node currRoot) { if (currRoot == null) { return; } printPostOrderRec(currRoot.left); printPostOrderRec(currRoot.right); System.out.print(currRoot.value + ", "); } } public class BinarySearchTreeDemo { public static void main(String[] args) { BinarySearchTree bst = new BinarySearchTree(); bst .insert(40) .insert(25) .insert(78) .insert(10) .insert(3) .insert(17) .insert(32) .insert(30) .insert(38) .insert(78) .insert(50) .insert(93); System.out.println("Inorder traversal"); bst.printInorder(); System.out.println("Preorder Traversal"); bst.printPreorder(); System.out.println("Postorder Traversal"); bst.printPostorder(); System.out.println("The minimum value in the BST: " + bst.findMinimum()); System.out.println("The maximum value in the BST: " + bst.findMaximum()); } }

## Summary

In this tutorial you would have got the very clear understanding on how to implement the **Binary Search Tree (BST)** in Java with various techniques. We have done good enough research on the binary search trees concept before writing this tutorial. I hope you have enjoyed reading this tutorial. If you have any questions, please write it in the comments section.

**Have you worked on binary search tree implementation in your company project?. Please share your experience with us.**

books:

Ajk_P says

Very well written explanation with pictures.

A small explanation about when we would want to use a BST and the time/space complexity of the operations could come in handy.

Keep up the good work.

Krishna Srinivasan says

HI,

Thank you for reading our blog

Tjay says

Thanks for providing this…

James says

it has an error? how can i fix it?

java:25: illegal start of type

Node node = new Node(value);

^

1 error

Process completed.

please help me.

Sheriff says

The pictures made the explanation and understanding the concepts very easy. Excellent. Looking forward with other data structures

Raj says

What if I insert the following records. This is not BST

bst .insert(40);

.insert(40);

.insert(40);

Harish B.N says

Nice explanation with working sample code ! Good Job

kantesh says

Hi

Thanks a lot, it is really helpful

udit says

The best thing in this blog is it’s Simplicity.Nice blog

Krishna Srinivasan says

Hi Udit,

Nice to see your comments.

– Krishna

Udit says

The blog is really awesome keep it going bro.Right now I am looking for similar stuff on Data Structure in java.Have you post any such more blogs on graph,m tree, and other important Algorithms of data structure.

Udit says

If you such more link ,please feel free to share thanks

regards

Udit

Krishna Srinivasan says

Hi Udit,

Glad to know that this post has helped you. We will work on few more post on this data structure . Could you suggest any specific post on this subject?

Thank You,

Krishna

Elamaran says

Thanks,simple explanation.

Krishna Srinivasan says

Hello Elamaran,

Thank You.

– krishna

Priya says

Clear explanation!

Krishna Srinivasan says

Hello Priya,

Thank you for the comments.

– krishna

Salas says

First of all: Thanks for this explanation. It’s very clear and helpful.

I think the pre-order traversal example contains an error in the solution. You write “Applying the Preorder traversal for the give example we get: 40, 25, 10, 3, 17, 32, 30, 38, 78, 50, 78, 93.” The 78 is repeated, I believe the 2nd ’78’ shouldn’t be there.

Thanks!

Salas says

Ok, so now I realize that in the 3 examples of traversals, the 78 is repeated… but that’s not right… right? Traversals only “print” out each node once.

Sajal Gupta says

By Far the best blog about traversing BST. Very nice!!

Krishna Srinivasan says

Hello Sajal,

Thank you for the comments.

– Krishna

Sajal says

Hi

Was just wondering if you could add level order traversal as well?

emrah says

It was a great tutorial for introducing binary search tree with great hands-on examples. Thanks a lot for your effort.

Krishna Srinivasan says

HI,

Thank you for your comments.

– Krishna

Chintan says

How does it know that currNode.left has to traverse left side and not right ?