Question

Considering the binary search tree data structure, give non-recursive implementations of min(), max(), floor(), ceiling(), rank(), and select().

Answer 1

Here I provided the code with all the required implementations required, comments have the explanation of the code.

CODE:

// C program to demonstrate insert operation in binary search tree
#include<stdio.h>
#include<stdlib.h>
#include<climits>

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

// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d \n", root->key);
inorder(root->right);
}
}

struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);
  
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
  
/* return the (unchanged) node pointer */
return node;
}

int minValue(struct node* node)
{
struct node* current = node;
  
/* loop down to find the leftmost leaf */
while (current->left != NULL)
{
current = current->left;
}
return(current->key);
}
  
int maxValue(struct node* node)
{
/* loop down to find the rightmost leaf */
struct node* current = node;
while (current->right != NULL)
current = current->right;
  
return (current->key);
}

void FloorCeil(node* root, node* &floor, node* &ceil, int data)
{
while (root)
{
// if node with key's value is found, both floor and ceil is equal
// to the current node
if (root->key == data)
{
floor = root;
ceil = root;
break;
}

// if given key is less than the root node, visit left subtree
else if (data < root->key)
{
// update ceil to current node before visiting left subtree
ceil = root;
root = root->left;
}

// if given key is more than the root node, visit right subtree
else
{
// update floor to current node before visiting right subtree
floor = root;
root = root->right;
}
}
}

/* Computes the number of nodes in a tree. */
int size(struct node* node)
{   
if (node==NULL)
return 0;
else   
return(size(node->left) + 1 + size(node->right));   
}

//rank of key k the number of keys that are less than k.
int rank_of(node *root, int val) {
int rank = 0;
while (root) {
if (val < root->key) // move to left subtree
root = root->left;
else if (val > root->key) {
rank += 1 + size(root->left); //size has number of nodes below it
root = root->right;
}
else
return rank + size(root->left);
}
return -1; // not found
}

int select_of(node *root, int k) {
//to get the kth smallest number
int count = 0;
if(k>size(root)){
return -1;
}
  
int ksmall = INT_MIN; // store the Kth smallest
node *curr = root; // to store the current node
  
while (curr != NULL)
{
if (curr->left == NULL)
{
count++;
  
// if count is equal to K then we found the
// kth smallest, so store it in ksmall
if (count==k)
ksmall = curr->key;
  
// go to current's right child
curr = curr->right;
}
else
{
// we create links to Inorder Successor and
// count using these links
node *pre = curr->left;
while (pre->right != NULL && pre->right != curr)
pre = pre->right;
  
if (pre->right==NULL)
{
//link made to Inorder Successor
pre->right = curr;
curr = curr->left;
}
  
else
{
pre->right = NULL;
  
count++;
  
// If count is equal to K then we found
// the kth smallest and so store it in ksmall
if (count==k)
ksmall = curr->key;
  
curr = curr->right;
}
}
}
return ksmall; //return the found value
}

int main()
{
struct node *root = NULL;
int a[]= {13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18};

root = insert(root, a[0]);
for(int i=1;i<sizeof(a)/sizeof(int);i++){
insert(root,a[i]);
}

// print inoder traversal of the BST
//inorder(root);

//to find min and max of the BST
printf("minimum: %d \n",minValue(root) );
printf("Maximum: %d \n",maxValue(root) );

//to find floor and ceil
node *f = nullptr, *c= nullptr;
FloorCeil(root, f, c, 4); // here we are trying to print floor and ceil of 4
printf("floor: %d, ceil:%d\n",f->key,c->key ); //It gives a segmentation falut if either of the two doesn't exist

int r,s;
r=11;
s=5;
printf("Rank of %d is: %d \n",r,rank_of(root,11) ); //Rank -1 implies that key doesnt exist in BST
printf("Select of %d: %d \n",s,select_of(root,5) ); // if printed -1 it means, key with that rank is not possible
return 0;
}

Here I attach a screenshot of output.