Binary Search Tree

We would cover the Binary Search Tree implementation in Java under the following:

  1. Introduction to Binary Search Tree
  2. Java Program for Binary Search Tree
  3. Inserting into a Binary Search Tree
  4. Search for a key in Binary Search Tree
  5. Inorder Traversal of Binary Search Tree
  6. Complete Java Implementation of Binary Search Tree
  7. Performance of Binary Search Tree

 

1. Introduction to Binary Search Tree

A Binary search tree is a data structure that stores data in form of a tree. So there is a root node at the top, then left child and right child.

A binary search tree have the following properties for every node:

  • each node has at most two children
  • the left child is less than or equal to the root node (left child ≤ root node)
  • the right child is greater than or equal to the root (right  child ≥ root node)

An example of a binary search tree is given in Figure 1.0. You can check that it satisfies the above 3 properties.

 

Example of a Binary Search Tree

Figure 1.0: Example of a Binary Search Tree

 

2. Java Program for Binary Search Tree

We are going to write a class the implement the binary search tree in Java. The class would have the following methods:

void Insert(int key): inserts the specified key into the tree

boolean contains(int key): checks if the tree contains the specified key

void PrintInOrder(): prints all the keys in the tree in sorted order

 

3. Inserting into a Binary Search Tree – void Insert(int key)

To insert a key, we first check if the key is ≤ the current data. If yes, then we check if the left is null. If null, then we return false. Else recursively call the insert() method on the left child

If however, the key is > the root, then we do the same on the right child.

The java program is given below:

 

//Insert a key into a binary search tree
public void insert(int key) {
	if(key <= this.data) {   //Go left
		if(this.left == null) {
			this.left = new Node(key);
		}
		else {
			this.left.insert(key);
		}
	}
	else {	//Go right
		if(this.right == null) {
			this.right = new Node(key);
		}
		else {
			 this.right.insert(key);
		}			
	}
}

Listing 1.0: The Insert Method for a Binary Search Tree

 

 

4. Searching for a key in BST – boolean contains(int key)

This would first check if the key equals the current node data. If yes, just return true.

If no, check if the key is less than the current node data. If yes, then check the left child is null, and if null, return false. Else recursively call the contains() method on the left child.

Repeat the same procedure on the right child, if the key is greater than the current node.

The implementation of the contains method in java is given in Listing 1.1 below

 

//Check if binary tree contains the given key
public boolean contains(int key) {
	if(key == this.data) {
		return true;
	}
	if(key < this.data) { //check left child
		if(this.left == null) {
			return false;
		}
		else {
			return this.left.contains(key);
		}
	}
	else {  //check right child
		if(this.right == null) {
			return false;
		}
		else {
			return this.right.contains(key);
		}
	}
}

Listing 1.1: The contains() method for Binary Search Tree

 

5. void PrintInOrder()

The PrintInOrder() uses the InOrder traversal to print all the nodes of the binary search tree. The InOrder traversal first visits the left subtree, then the root, then the right subtree.

The Java implementation if quite easy to understand. It is given in Listing 1.2.

 

//PrintInorder uses InOrder traversal
public void PrintInOrder() {
	if(this.left != null) {
		this.left.PrintInOrder();
	}
	System.out.print(data + " ");
	if(this.right != null) {
		this.right.PrintInOrder();
	}
}

Listing 1.2: InOrder Printing of Binary Search Tree

 

6. Complete Implementation of Binary Search Tree in Java

You can find the complete program for Java Implementation of the binary search tree. Also, a test main method is provide. You can just copy and run the code.

 

public class Node {
	Node left;
	Node right;
	int data;
	
	public Node(int data) {
		this.data = data;
	}

	//Insert a key into a binary search tree
	public void insert(int key) {
		if(key <= this.data) {   //Go left
			if(this.left == null) {
				this.left = new Node(key);
			}
			else {
				this.left.insert(key);
			}
		}
		else {	//Go right
			if(this.right == null) {
				this.right = new Node(key);
			}
			else {
				 this.right.insert(key);
			}			
		}
	}
	
	//Check if binary tree contains the given key
	public boolean contains(int key) {
		if(key == this.data) {
			return true;
		}
		if(key < this.data) { //check left child
			if(this.left == null) {
				return false;
			}
			else {
				return this.left.contains(key);
			}
		}
		else {  //check right child
			if(this.right == null) {
				return false;
			}
			else {
				return this.right.contains(key);
			}
		}
	}
	
	//PrintInorder uses InOrder traversal
	public void PrintInOrder() {
		if(this.left != null) {
			this.left.PrintInOrder();
		}
		System.out.print(data + " ");
		if(this.right != null) {
			this.right.PrintInOrder();
		}
	}
	
	
	public static void main(String args[]) {
		int ar[] = {4,7,9,1, 11, 8, 3, 5};
		Node binarytree = new Node(8);
		
		for(int item : ar) {
			binarytree.insert(item);
		}
		
		binarytree.PrintInOrder();
	}
}

Listing 1.2: Complete implementation of Binary Search Tree in Java

 

7. Performance of Binary Search Tree

Both insert, delete and search operations take logarithmic time. This is means that the time complexity is order of logn – O(logn).

Space complexity if linear. That is O(n)