### 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

– Introduction To AlgorithmsNbe a node in a binary search tree. IfMis a node in theleftsubtree ofN, thenM.Value <= N.Value. IfMis node in the right subtree ofN, thenM.Value >= N.Value.

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.

- Create a node
**temp**and assign the**root**node to it. - If the temp node is
**null**, then simply**return null**and stop here as the given value is not present in the tree. - Compare the
**given value****X**with the**temp node’s value**. - 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. - 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.

- Assign the
- 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.

- Assign the

### 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: