Binary Search Tree

A Binary Search Tree (BST) is a tree in which all nodes have the properties listed below: 

• The left sub-tree of a node has a key that is less than or equal to the key of its parent node.
• A node's right sub-tree has a key that is greater than its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Representation of Binary Search Tree.

BST is a set of nodes organized in such a way that they all have the same BST qualities. A key and a value are assigned to each node. The required key is compared to the keys in BST during the search, and if found, the related value is obtained.

Following is a pictorial representation of BST −

We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.

Basic Operations

Following are the basic operations of a tree −

• Search − Searches an element in a tree.
• Insert − Inserts an element in a tree.
• Pre-order Traversal − Traverses a tree in a pre-order manner.
• In-order Traversal − Traverses a tree in an in-order manner.
• Post-order Traversal − Traverses a tree in a post-order manner.

Node

• Define a node having some data, references to its left and right child nodes.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Search Operation

• Start searching for an element from the root node whenever possible. 
• Then, if the data is less than the key value, look in the left subtree for the element. 
• If not, look for the element in the right subtree. For each node, use the same algorithm.

Algorithm for Serching.

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }//else go to right tree
         else {                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   return current;
}

Insert Operation

• Before inserting an element, make sure it's in the right place. 
• Begin your search at the root node, then look for an empty spot in the left subtree and insert the data if the data is less than the key value. 
• If not, look find an empty place in the right subtree and fill it in.

Algorithm

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}