Binary Search Tree Representation

The Binary Search Tree has a unique behavior. The value of a node's left child must be less than the value of its parent, and the value of the node's right child must be bigger than the value of its parent.

Tree Node

• The code to write a tree node would be similar to what is given below. It has a data part and references to its left and right child nodes.

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

• In a tree, all nodes share a common construct.

BST Basic Operations

The basic operations that can be performed on a binary search tree data structure are the following −

• Insert − Inserts an element in a tree/create a tree.
• Search − Searches an element in a tree.
• Preorder Traversal − Traverses a tree in a pre-order manner.
• Inorder Traversal − Traverses a tree in an in-order manner.
• Postorder Traversal − Traverses a tree in a post-order manner.

We shall learn to create (insert into) a tree structure and search a data item in a tree in this chapter.

Insert Operation

• The tree is created by the very first insertion. After that, whenever an element needs to be placed, make sure it's in the right place first. 
• Begin your search at the root node, then look for an empty place 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

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If      

Implementation

• The implementation of insert function should look like this −

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, create root node
   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;
            }
         }
      }            
   }
}

Search Operation

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

Algorithm

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node

   endwhile 
   
   return data not found
   
end if      

• The implementation of this algorithm should look like this.

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;
   }  
}