Trees are fundamental data structures in computer science, and in this article we’ll explore the **Binary Search Tree.**

Before we dive into our **binary search tree java implementation**, let’s get a clear understanding of what a tree is, and when it is used.

As mentioned, trees are heavy used in the world of computer science. Some of the applications of the tree data structure is:

- Files in operating systems are almost always stored in trees, or data structures similar to a tree.
- Trees are often used when designing compilers.
- Application where text processing is used.
- Search algorithms often depend on trees.

## What is a Binary Search Tree?

Let’s start off by explaining what a general tree is. We’ll ignore the “binary search” to begin with.

The tree data structure can easily be understood if you visualize a traditional family tree, where you have *parents *and *children.
*Between the entities (nodes) in the family tree, there are relationships.

Now, let’s disregard the family tree, and focus on the actual tree data structure.

A tree data structure is composed of two things: **nodes, **and **edges **that connect the nodes.

The properties of a tree is as follows:

- One node is the “master-parent”, known as the
**root node.**All the other nodes are inheritors of the root node. - Every node is connected to another node by exactly
**one edge.** - Each and every node has a
**unique path**back up to the**root node.**

The picture above is an example of a tree. Note that this is **NOT **a Binary Search Tree.

The node at the top, node A, is the root. All other nodes are inheritors of this node.

Nodes below the root node, are connected through lines. These lines are the **edges **that connect the nodes.

Now, how does the Binary Search Tree differ from a regular tree?

- A node can only have two children, thus
**binary.** - The left subtree of a node can only contain nodes which are
**less than**the parent node’s key. - The right subtree of a node can only contain nodes which are
**more than**the parent node’s key. - The left and right subtree each must also be a binary search tree.
- There can’t be any
**duplicate**nodes.

The picture above is a Binary Search Tree.

The tree’s root is the node with key 4. All nodes to the left of root are less than 4, and all nodes to the right are more than 4.

## Binary Search Tree implementation in Java

Note that we’ll also write tests for our Binary Search Tree, using **JUnit**.

### The Node Class

A binary search tree consists of nodes, where each node can have a maximum of two children. Let’s implement our **Node class.**

/** * Node in a Binary Search Tree. * The node contains a key (it's value), and a reference to the right and left node (its children). * <p> * The variables in the class are package-private. No getter's and setter's needed. * * @author Anders Engen Olsen */ class Node<AnyType> { AnyType value; Node<AnyType> left, right; Node(AnyType value) { if (value == null) throw new IllegalArgumentException("Value can't be null"); this.value = value; left = right = null; } }

import org.junit.Before; import org.junit.Test; import static org.junit.Assert.*; /** * Test for the Node class. * * @author Anders Engen Olsen * @see Node */ public class NodeTest { private Node<Integer> node; private Integer nodeValue; @Before public void setUp() { nodeValue = 1; node = new Node<>(nodeValue); } @Test public void testNodeHasCorrectValue() { assertEquals(nodeValue, node.value); } @Test public void testNodeHasNoChildren() { assertNull(node.left); assertNull(node.right); } @Test(expected = IllegalArgumentException.class) public void testNodeNullConstructorThrowsException() { Node<Integer> node = new Node<>(null); } }

### The BinarySearchTree Class

Let’s implement the **BinarySearchTree.java**, one operation at a time.

Remember that we’ll be implementing three common operations for a binary search tree – **search, insert and delete.**

We start off by creating a skeleton for the BinarySearchTree class.

/** * Binary Search Tree. * * @author Anders Engen Olsen */ public class BinarySearchTree<AnyType> { private Node<AnyType> root; private int size; /** * Default constructor, constructing an empty tree. */ public BinarySearchTree() { root = null; size = 0; } /** * Returning size of the search tree * * @return size */ public int size() { return size; } /** * @return true if tree is empty, size = 0. */ public boolean isEmpty() { return size == 0; } /** * Searching for a node in the bst * * @param x The value to search for * @return true if found */ public boolean find(AnyType x) { return false; } /** * Deleting a node in the best * * @param x The value to delete * @return true if found and deleted */ public boolean delete(AnyType x) { return false; } /** * Inserting a Node in the binary search tree. * * @param x value to insert */ public void insert(AnyType x) { } }

As always, tests are written!

import org.junit.Before; import org.junit.Test; import static org.junit.Assert.*; /** * Test for the BinarySearchTree class. * * @author Anders Engen Olsen * @see BinarySearchTree */ public class EmptyBinarySearchTreeTest { private BinarySearchTree<Integer> bst; @Before public void setUp() { bst = new BinarySearchTree<>(); } @Test public void testBstHasSizeOfZero() { assertEquals(0, bst.size()); } @Test public void testBstIsEmptyReturnsTrue() { assertTrue(bst.isEmpty()); } }

Now that we’ve made the class skeleton, and assured ourselves that it’s working as expected, we can implement the operations.

### Insert Operation

We want the following behavior for our insert operation:

- We must first find the correct place to insert the node.
- Start traversing the BST from root.
- Compare root.value with the value passed to the method, the value
**X.** - If root.value is greater than
**X,**go to the left sub tree. - If root.value is less than
**X,**go to the right sub tree. - If we reach a
**null**value, we have found the correct place to insert a new node.

### Find Operation

The find (search) operation is a simple operation to perform, and very similar to the **insert **operation. It runs in O(logN).

NB! If you are unfamiliar with Big-Oh notation, check out **Introduction to Algorithm Analysis**.

For our find operation, we want the following behavior:

- Start from the root node and compare root.value with the value passed into the method, the value
**X**. - If root.value is greater than
**X,**we need to go to the left sub tree. - If root.value is less than
**X,**we need to go to the right sub tree. - If we encounter a value which is equal to
**X,**we terminate and return true. - If we encounter a
**null**value, we have traversed the whole tree, and return false.

### Delete Operation

The delete operation is the most complicated operation we’ll implement in this tutorial.

A total of 3 cases can occur when deleting a node from a Binary Search Tree.

- The node to delete is a leaf node (meaning it has no children).
- The node to delete has one child.
- The node to delete has two children.

If we’re deleting a **leaf node**, all we have to do is to delete that node. Since the node has no children, we don’t have to worry about “reconnecting” other nodes.

When deleting a leaf node, all we have to do is to make parent.right / parent.left = **null**, according to the leaf node’s position.

When deleting a node with **one child, **it is slightly more complicated. Let’s say we want to delete **nodeX.**

- Traverse to
**nodeX**, and keep track of the parent of**nodeX**. You must also keep track of which side**nodeX**exists in its parent (left or right). - Check which of the sides of
**nodeX**is**null.**Remember, one of the sides must be null, since we’re deleting a node with only one child. - Connect nodeX’s “not null” child to nodeX’s parent.

The hardest case is when we are deleting a node with **two children.
**

To delete a node with two children, one must find the **successor.**

Successor is the node which will replace the deleted node. Now the question is to how to find it and where to find it.

*Successor is the smaller node in the right sub tree of the node to be deleted.*

### Final Implementation of the Binary Search Tree in Java

Note that some of the methods make use of private recursive methods!

New to recursion? Check out our **introduction to recursion**.

import java.util.NoSuchElementException; /** * Binary Search Tree. * * @author Anders Engen Olsen */ public class BinarySearchTree<AnyType extends Comparable> { private Node<AnyType> root; private int size; /** * Default constructor, constructing an empty tree. */ public BinarySearchTree() { root = null; size = 0; } /** * Returning size of the search tree * * @return size */ public int size() { return size; } /** * @return true if tree is empty, size = 0. */ public boolean isEmpty() { return size == 0; } /** * Searching for a node in the bst * * @param x The value to search for * @return true if found */ public boolean find(AnyType x) { return findRecursively(root, x); } /** * Private recursive method to findRecursively a value in the BST * * @param root root node * @param x value to findRecursively * @return true if found value == x. */ private boolean findRecursively(Node<AnyType> root, AnyType x) { // If root is null the node is not present if (root == null) return false; // It is present if (root.value.compareTo(x) == 0) return true; // The value is greater if (root.value.compareTo(x) > 0) return findRecursively(root.left, x); // The value is less return findRecursively(root.right, x); } /** * Deleting a node in the best * * @param x The value to delete * @return true if found and deleted */ public Node<AnyType> delete(AnyType x) { return deleteRecursively(root, x); } /** * Deleting recursively * * @param root root node * @param x value to delete * @return deleted node */ private Node<AnyType> deleteRecursively(Node<AnyType> root, AnyType x) { // Traversed the whole tree, returning false if (root == null) throw new NoSuchElementException("Not found!"); // Traversing if (x.compareTo(root.value) < 0) root.left = deleteRecursively(root.left, x); else if (x.compareTo(root.value) > 0) root.right = deleteRecursively(root.right, x); else { size--; // node with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node with two children: Get the inorder successor (smallest // in the right subtree) root.value = minValue(root.right); // Delete the inorder successor root.right = deleteRecursively(root.right, root.value); } return root; } AnyType minValue(Node root) { AnyType minv = (AnyType) root.value; while (root.left != null) { minv = (AnyType) root.left.value; root = root.left; } return minv; } /** * Inserting a Node in the binary search tree. * * @param x value to insert */ public void insert(AnyType x) { root = insertRecursively(root, x); size++; } /** * Private recursive method to insert a node. * * @param root * @param x * @return */ private Node<AnyType> insertRecursively(Node<AnyType> root, AnyType x) { // Tree is empty, inserting at root if (root == null) { root = new Node<>(x); return root; } // Traversing the tree recursively if (x.compareTo(root.value) < 0) root.left = insertRecursively(root.left, x); else if (x.compareTo(root.value) > 0) root.right = insertRecursively(root.right, x); else { // Duplicate element! throw new IllegalArgumentException("No duplicates allowed!"); } return root; } }

import org.junit.Before; import org.junit.Test; import java.util.NoSuchElementException; import static org.junit.Assert.*; /** * Test for the BinarySearchTree. * * @author Anders Engen Olsen */ public class BinarySearchTreeTest { private BinarySearchTree<Integer> bst; @Before public void setUp() { bst = new BinarySearchTree<>(); } @Test public void testInsertElementInBSTSizeIncreases() { bst.insert(1); assertEquals(1, bst.size()); } @Test(expected = IllegalArgumentException.class) public void testInsertDuplicateThrowsException() { populateBST(); bst.insert(1); } @Test public void testTenElementsGiveSizeOfTen() { populateBST(); assertEquals(10, bst.size()); } @Test public void testFindElementInBSTTrueWhenPresent() { populateBST(); assertTrue(bst.find(4)); } @Test public void testFindElementInBSTFalseWhenNotPresent() { populateBST(); assertFalse(bst.find(11)); } @Test public void testDeleteElementSizeDecreases() { populateBST(); bst.delete(1); assertEquals(9, bst.size()); } @Test(expected = NoSuchElementException.class) public void testDeleteNotPresentThrowsException() { populateBST(); bst.delete(11); } /** * Populating the BST with 0-9, total of 10 elements. */ private void populateBST() { for (int i = 0; i < 10; i++) { bst.insert(i); } } }