Data Structures and Algorithms Problem Operations on BSTs. Write a recursive fun

Question

Data Structures and Algorithms Problem

Operations on BSTs. Write a recursive function that returns the minimum key value in a binary search tree of distinct (positive) integers. Return -1 in case the tree is empty. Write a recursive function that returns the predecessor of the key value k in a binary search tree of distinct (positive) integers. This is the key value that precedes k in an inorder traversal of the tree. If k does not exist, or if k has no predecessor, your function should return -1.

Explanation / Answer

(a) Program to return minimum key value.

#include <stdio.h>
#include<stdlib.h>

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

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return -1 */

if (node == NULL)
return -1;
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

  
return node;
}
}

int minValue(struct node* node) {
struct node* current = node;

while (current->left != NULL) {
current = current->left;
}
return(current->data);
}

(b) program to return the predecessor of the key in BST:

#include <iostream>
using namespace std;

struct Node
{
int key;
struct Node *left, *right;
};

// This function finds predecessor of key in BST.
void findPreSuc(Node* root, Node*& pre,int key)
{
if (root == NULL) return ;

// If key is present at root
if (root->key == key)
{
// the maximum value in left subtree is predecessor
if (root->left != NULL)
{
Node* tmp = root->left;
while (tmp->right)
tmp = tmp->right;
pre = tmp ;
}

return -1;
}

// If key is smaller than root's key, go to left subtree
if (root->key > key)
{
findPre(root->left, pre,key) ;
}
else
{
pre = root ;
findPreSuc(root->right, pre, suc, key) ;
}
}
Node *newNode(int item)
{
Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

/* A utility function to insert a new node with given key in BST */
Node* insert(Node* node, int key)
{
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}

int main()
{
int key = 65; //Key to be searched in BST
Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);


Node* pre = NULL, *suc = NULL;

findPreSuc(root, pre, suc, key);
if (pre != NULL)
cout << "Predecessor is " << pre->key << endl;
else
{
return -1;
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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