What is a Binary Search Tree?

In computer science, Binary Search Tree or BST is a binary tree in which each node follows the following property:

Let N be a node in a binary search tree. If M is a node in the left subtree of N, then M.Value <= N.Value. If M is node in the right subtree of N, then M.Value >= N.Value.

– Introduction To Algorithms

For instance, in the above tree, the value of node 20 is greater than all the nodes in left sub-tree (10,13,16,18) and smaller than all nodes in the right sub-tree (26,34,36,40). And the same is true for every other node in the tree.

In this lesson we will learn how to search values in a Binary Search Tree.

Formal Algorithm 

Let’s suppose you would like to search for value X in the tree.

1. Create a node temp and assign the root node to it.
2. If the temp node is null, then simply return null and stop here as the given value is not present in the tree.
3. Compare the given value X with the temp node’s value.
4. If the given value is equal to the temp node’s value then you have found the correct node, so simply return the temp node.
5. If the given value is greater than the temp node’s value then:
   • Assign the right child to the temp node and go to step 2.
6. If the given value is smaller than the temp node’s value then:
   • Assign the left child to the temp node and go to step 2.

Visualize the Search Algorithm

Suppose we have the following Binary Search Tree (BST):

We would like to search the value 49 in the tree.

Iteration 1:

We will start the search process with the root node 60. As the value 49 is smaller than 60,  therefore we can ignore the right sub-tree and move to the node 35.

Iteration 2:

Now we are at node 35. As the value 49 is greater than 35, therefore we can ignore it’s left sub-tree and move to the node 49.

Iteration 3

Similarly again, we will compare the given value 49 with node 49. As the value 49 is equal to the current node’s value 49, therefore we have found our value in the given tree and hence can stop here.

Implementation in Java Language

//Java program to implement insertion procedure of a Binary Search Tree (BST)

public class BST{

	//class for a single node of the tree
	static class Node{
		int data;	//data value
		Node left;	//left child
		Node right;	//right child

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

	//root node of the tree
	static Node root;

	//function to find specific data elements in the tree.
	public static Node search(int valueToSearch){

		// create a temp node and assign root to it.
		Node temp = root;
		
		// repeat until we find the value or temp is null
		while(temp!=null){
                        
			// we found the value so we can stop here
			if(temp.data == valueToSearch){
				return temp;
			}
 
			// if temp node's value is greater than 
			// given value then move to left sub tree
			// otherwise to the right subtree.
			if(temp.data > valueToSearch){
				temp = temp.left;
			}
			else{
				temp = temp.right;
			}
		}

		// return the found node, null if we dont found
		// the value in the tree.
		return temp;
	}


	//method to insert the value in the BST.
	public static void insert(int value){
		//create a new node with the given value
		Node node = new Node(value);

		//create a temp node 
		Node temp = root;

		//if root is null 
		//then assign root = node
		if(temp==null){
			root = node;
			return;
		}

		//repeat until correct position is found
		while(temp!=null){

			//if value is greater than temp's value
			if(temp.data<value){
				//if right child is null
				//then attach new node as its right child
				if(temp.right==null){
					temp.right = node;
					return;
				}

				//else move to the right child
				temp = temp.right;
				continue;
			}


			//if value is smaller than temp's value	
			if(temp.data>value){
				//if left child is null
				//then attach new node as its left child
				if(temp.left==null){
					temp.left = node;
					return;
				}

				//else move to the left child
				temp = temp.left;
			}
		}
	}

	//method to traverse the BST in inorder fashion
	public static void inorder(Node node){
		if(node==null){
			return;
		}

		inorder(node.left);
		System.out.print(node.data + " ");
		inorder(node.right);
	}

	//main method to run the program.
	public static void main(String [] args){

		//values to insert
		int [] array = {20,16,34,10,18,26,40,13,36,19};

		//insert one by one
		for(int i=0;i<array.length;i++){

			System.out.println("------------------------------");
			System.out.println("Inserting value : " + array[i]);

			//insertion
			insert(array[i]);

			System.out.println();

			System.out.println("Inorder Traversal of BST after insertion.\n");

			//inorder traversal
			inorder(root);

			System.out.println("\n");
		}

		// search for the value
		int valueToSearch = 19;
		Node foundNode = search(valueToSearch);

		if (foundNode != null){
			System.out.println("Found value : " + foundNode.data);    
		}
		else{
			System.out.println("Value not found!");
		}
	}
}

Time Complexity

When the tree is balanced then the max depth of the tree can be the logarithm of the number of nodes in the tree. Therefore the number of comparisons for searching the given value would be log(n). As a result, the best case time-complexity would be O(log(n)) where n is the number of nodes in the tree.

But in the worst case, if the values are inserted in sorted order then the tree would become skewed. Therefore we need n comparisons to search the given value. As a result, the worst-case time complexity would become O(n).

Full code –> Binary Search Tree with all other methods.

Next learn about tree traversals:

• Inorder Traversal
• Preorder Traversal
• Postorder Traversal
• Levelorder Traversal