Consider a binary search tree T with nodes containing the four fields key, lengt

Question

Consider a binary search tree T with nodes containing the four fields key, length, left child and right child, where key is an integer number (the tree is organized with respect to key values), length is the length of the longest path from this node to a leaf, left child, and right child are pointers to the subtrees.

Design an algorithm for a procedure insert(T, num) that inserts to a binary searches tree T a new node with the key value num (you can assume that a node with key = num is not in the tree) and updates length fields accordingly. The function should work in O(h) time, where h is the length of the access path.

Explanation / Answer

I am pasting below whole code just for better understading you can refer to add function(actual Algorithm)from code which take 4 parameters its add(node* *hd, int key,int *length_update,int check_leaf) where hd is addres of root node of tree,key is the value to be inserted in Tree,length_update is the address of value from which the length should be incresed,check_leaf is for checking whether we should update length or not. Now in add function while adding new element we go either left of current element or right of current element so at every level we go to either direction but not in both direction.So add function add new element in binary search tree and update length of its parent node if required in O(h).

Code:

/********************************************************************************************************
* File Name : btree.c
* Creation Date : 11-11-2015
* Last Modified : Wednesday 11 November 2015 01:22:01 AM IST
* Ability opens one door ,second door but not the last door Its the ATTITUDE which opens last one   *
*                                                   *
********************************************************************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
   int key;
   int length;
   struct node *left;
   struct node *right;
}node;
void print(node *head){ // printing Inorder of tree
   if (head){
       print(head->left);
       printf("%d -> %d ",head->key,head->length);
       print(head->right);
   }
}
void add(node* *hd, int key,int *length_update,int check_leaf){
   node* curr = *hd;
   if(curr == NULL){
       curr = malloc(sizeof(node)); // creating new node
       curr->left = curr->right = NULL;
       curr->key = key;
       curr->length = 0; // as this is leaf node so its length is zero
       if (check_leaf == 1){ // if check_leaf = 1 then length of all of its parent will be updated
           *length_update = 1;
       }
       *hd = curr; // add current node to the tree
   }else{
       if(key < curr->key){
           if (curr->right == NULL){ // Case1.while adding node as a left child length of parents will be updated only if right child of current node is null
               check_leaf = 1;
           }
           add(&curr->left, key,length_update,check_leaf);
           if (*length_update >= 1){ // updating length of all parents of newly added child
               curr->length = *length_update;
               *length_update += 1; // adding one beacuse its parents will have +1 of current length
           }
       }else{
           if(curr->left == NULL){ // case2.while adding node as a right child length of parents will be update only if left child of current node is null
               check_leaf = 1;
           }
           add(&curr->right, key,length_update,check_leaf);
           if (*length_update >= 1){ // updating length of all parents of newly added child
               curr->length = *length_update;
               *length_update += 1; // adding one beacuse its parents will have +1 of current length
           }
       }
   }
}
int main()
{
   int n;
   printf ("Enter Number of node in Binary Search Teee:");
   scanf("%d",&n);
   int i,x;
   node * head = NULL; // Head of the tree
   int length_update = 0;
   printf ("Enter %d elements to be inserted in binary search tree :",n);
   for(i = 0;i < n;i++){
       scanf("%d",&x); // x is element to be inserted in tree
       add(&head,x,&length_update,0); // adding element in tree
       length_update = 0; // everytime making 0 because we would have to update length with reference to newly added child
   }
   printf("Node -> Length ");
   print(head); // printing Inorder of tree with key and height
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.