What is a Binary search tree? How to implement it?

Binary Search Tree

Binary Search Tree is one of most applicable principle using binary trees. Binary Search Tree is a special case of binary tree. It is used to store elements in the sorted order. Binary search tree are often used in the backend of many applications like database server and other data record management applications.

Data Structure

Binary Search Tree also uses same data structure as it is used for simple binary tree. There is a member to hold the value in the structure and two pointers called left and right to hold the reference for left and right sub nodes.

struct node {
  int         value;
  struct node *left;
  struct node *right;
};

Adding a node

Allocation of a new node is done with the same logic as normal binary tree node allocation. Now a new record is allocated it should be compared with the parent node and placed in the left sub tree if its value is less than parent else that is placed in the right sub tree. This addition is recursive in nature and comparison goes from root to lower sub tree level till the condition is reached.

struct node * new_node(int val)
{
    struct node * new_node = (struct node *)malloc(sizeof(struct node));
    if(new_node)
    {
       new_node->value = val;
       new_node->left = 0;
       new_node->right = 0;
    }
    else
    {
      exit(-1);
    }
    return new_node;
}
struct node * insert(struct node * root, int value)
{
  if(root ==  NULL)
  {
    return new_node(value);
  }
  else
  {
    if(value == root->value)
    {
      printf("Value already there!");
      return NULL;
    }
    if(value < root->value)
    {
      root->left = insert(root->left, value);
    }
    else
    {
      root->right = insert(root->right, value);
    }
    return root;
  }
}

Printing/Traversing Tree

Traversal of binary search tree is done with in-order fashion. Every node has a value greater than its left node and less than that of right node. We have populated entire tree in this way and thus nodes are arranged in a sorted manner. Now iterating through the entire tree is easy and can be done simply visiting left sub tree then the node value and then right sub tree. This way we can print all the nodes in the tree.

void printout(node * tree) {
  if(tree->left) {
    printout(tree->left);
  }
  printf("%d ",tree->value);
  if(tree->right) {
    printout(tree->right);
  }
}

int main(int argc, char* argv[])
{
  struct node * head = NULL;
  int array[] = { 9, 6, 3, 5, 2, 1, 9, 0, 4, 50, 30,};
  for(int i = 0; i < sizeof(array)/sizeof(int); i++)
  {
    if(head == NULL)
    head = insert(head, array[i]);
    else
      insert(head, array[i]);
  }
  printout(head);
 return 0;
}

Node Lookup

We can also lookup for a node by comparing the required value with left child then with its own node and then with right child. This iteration will start from root and will go recursively into the sub tree level till our node is found. This is the way to check if a the value is already present in the tree.

struct node * lookup(struct node * root, int value)
{
  if(root ==  NULL)
  {
    return NULL;
  }
  else
  {
    if(value == root->value)
    {
      printf("node found!");
      return root;
    }
    if(value < root->value)
    {
      return lookup(root->left, value);
    }
    else
    {
      return lookup(root->right, value);
    }
  }
}

Finding Minimum Value

Nodes in Binary Search Tree are arranged in such a way that left of any node contains the lesser value. In this way if we take the left most node in the max depth level then that would contain the least value. Our logic goes in the same way. We iterate to node->left untill we hit NULL then we can find the Min Value.
int min_value (struct node* node) { 

  /* loop down to find the leftmost leaf */
  while (node->left != NULL) { 
    node = node->left; 
  } 
  return (node->data); 
}

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions