Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 10 M

Year: Dec 2014

• A binary search tree is a variant of binary tree wherein the nodes are arranged in an order.
• In a BST, all the nodes in the left sub-tree has a value less than the value of the root node. Similarly, all the nodes in the right sub-tree has a value that is greater than the root node.
• This same rule is applicable to every sub-tree in the tree.

• To display a binary search tree in non-decreasing order, we need to carry out an in-order traversal.

• The output of in-order traversal is:

  8, 12, 16, 18, 19, 25, 29, 36, 32, 45

  #include<stdio.h>
  #include<conio,h>
  #include<malloc.h>
  struct node
  {
  int data;
  struct node *left;
  struct node *right;
  };
  
  struct node *binary_tree;
  void inorder_traversal(struct node *binary_tree)
  {
  if(binary_binary_tree!=NULL)
  {
      inorder_traversal(binary_tree-->left);
      printf("%d \t",binary_tree-->data);
      inorder_traversal(binary_tree-->right);
  }
  }
  
  struct node *insert_data(struct node *binary_tree, int value)
  {
  struct node *ptr,*parent_ptr,*node_ptr;
  ptr=(struct node *)malloc(sizeof(struct node));
  ptr-->data=value;
  ptr-->left=NULL;
  Ptr-->right=NULL;
  if(binary_tree==NULL)
  {
      binary_tree=ptr;
      binary_tree->left=NULL;
      binary_tree->right=NULL;
  }
  else
  {
      parent_ptr=NULL;
      node_ptr=binary_tree;
      while(node_ptr!=NULL)
      {
          parent_ptr=node_ptr;
          if(val< node_ptr->data)
              node_ptr=node_ptr->left;
          else
              node_ptr =node_ptr->right;
      }
      if(val< parent_ptr->data)
          parent_ptr->left=ptr;
      else
          parent_ptr->right=ptr;
  
  
  }
  return binary_tree;
  }
  
  void create_binary_tree(struct node *binary_tree)
  {
  binary_tree=null;
  }
  
  int main()
  {
  struct node *ptr;
  int;
  create_binary_tree(binary_tree);
  printf("enter number of elements in the BST");
  scanf("%d",no_elements);
  for(i=0;i<no_elements;i++)
  {
      printf("\n enter the value of new node");
      scanf("%d",&val);
      binary_tree=insert_data(binary_tree,val);
  }
  printf("\n the elemets of binary_tree in non-decreasing order is :");
  printf("\n");
  inorder_traversal(binary_tree);
  getch();
  return 0;
  }