Question

In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order traversal, preorder traversal, and find.

Please separate the code in the four parts and explain in detail what is happening. Also, if you can please basic C language. If not, then I understand. Thank you for your time.

The test cases are 'm', 'd', 'g', 'r', 'p', 'b', and 'x'.

Output:

Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: i

Enter new node's key value: H

Enter string of up to 10 characters for 'H's data: Hello

  Pre-order traversal is: H
  Inorder traversal is: H

Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: i

Enter new node's key value: W

Enter string of up to 10 characters for 'W's data: Wow

  Pre-order traversal is: H W
  Inorder traversal is: H W

Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: i

Enter new node's key value: F

Enter string of up to 10 characters for 'F's data: Fine

  Pre-order traversal is: H F W
  Inorder traversal is: F H W

Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: f

Enter the search key: H

  Found the string "Hello" there.

Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: f

Enter the search key: x

  'x' is not in the tree

Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: q

Answer 1

Please find the C code as following -

#include<stdio.h> 
#include<stdlib.h> 
   
struct node 
{ 
    int key; 
    char string[10];
    struct node *left, *right; 
}; 
   
// A utility function to create a new BST node 
struct node *newNode(int item,char string[]) 
{ 
    struct node *temp =  (struct node *)malloc(sizeof(struct node)); 
    temp->key = item; 
    for(int i=0; i<10;i++){
      temp->string[i] = string[i];
    }
    temp->left = temp->right = NULL; 
    return temp; 
} 
  
   
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key, char string[]) 
{ 
    /* If the tree is empty, return a new node */
    if (node == NULL){
      return newNode(key,string); 
    }
  
    /* Otherwise, recur down the tree */
    if (key < node->key) 
        node->left  = insert(node->left, key,string); 
    else if (key > node->key) 
        node->right = insert(node->right, key,string);    
  
    /* return the (unchanged) node pointer */
    return node; 
} 
   
char* find(struct node *root, int key){
  if(root==NULL)
    return NULL;
  if(root->key == key){
    return root->string;
  }
  else if(key<root->key)
    return find(root->left,key);
  else
    return find(root->right,key);
}

// Driver Program to test above functions 
int main() 
{ 
    char choice='q',value;
    char key;
    
    struct node *root = NULL;
    while(1){
      char string[10];
      printf("\nEnter choice(lower cse is aslo acceptable)---(I)nsert,(F)ind,(Q)uit: ");
      scanf(" %c",&choice);
      if(choice=='i'||choice=='I'){
        printf("\nEnter new node's key value: ");
        //input key value of the node
        scanf(" %c",&value);
        printf("\nEnter String of up to 10 characters for ");printf(" %c's data: ",value);
        fflush(stdin);
        //input string for the node having 10 chars as maximum
        scanf("%10s",string);
        fflush(stdin);
        root = insert(root,value,string);
      }
      else if(choice=='f'||choice=='F'){
        printf("\nEnter the search key: ");
        scanf(" %c",&key);
        char *val = find(root,key);
        //if node carrying key to be searched found
        if(val!=NULL)
          printf("\nFound the string \"%s\" there.",val);
        //if node not found
        else
          printf("\n'%c' is not there.",key);
      }
      else 
        break;
    }
    return 0; 
} 

Sample output is as folllowing:-