Question

Hello, I need help implementing the c++ code for successor and predecessor of a BST following the pseudocode below, thank you for your help in advance.

TREE-SUCCESSOR (x) l if, right[x]〆NIL 2 then return TREE-MINIMUM(right[x]) 3 y ←p[x] 4 while y NIL and x = right[y] ply] 7 return y The code for TREE-PREDECESSOR is similar.

struct treeNode

{

int data;

treeNode *left;

treeNode *right;

};

treeNode* FindMin(treeNode *node) /* find the minumum node */

{

while (node->left != NULL)

{

node = node->left;

}

return node;

}

treeNode* FindMax(treeNode *node) /* find the maximum node */

{

while (node->left != NULL)

{

node = node->right;

}

return node;

}

Answer 1

C++ code:

// C++ program to find predecessor and successor in a BST

#include <iostream>

using namespace std;

// BST Node

struct treeNode{

int data;

treeNode *left;

treeNode *right;

};

treeNode* FindMin(treeNode *node) /* find the minumum node */

{

while (node->left != NULL){

node = node->left;

}

return node;

}

treeNode* FindMax(treeNode *node) /* find the maximum node */

{

while (node->left != NULL){

node = node->right;

}

return node;

}

// This function finds predecessor and successor of key in BST.

// It sets pre and suc as predecessor and successor respectively

void findPreSuc(treeNode* root, treeNode*& pre, treeNode*& suc, int key )

{

// Base case

if (root == NULL) return ;

// If key is present at root

if (root->data == key)

{

// the maximum value in left subtree is predecessor

treeNode *temp=FindMin(root->right);

}

// the minimum value in right subtree is successor

if (root->right != NULL)

{

treeNode* tmp = FindMax(root->left);

  

}

// If key is smaller than root's key, go to left subtree

if (root->data > key)

{

suc = root ;

findPreSuc(root->left, pre, suc, key) ;

}

else // go to right subtree

{

pre = root ;

findPreSuc(root->right, pre, suc, key) ;

}

}

// A utility function to create a new BST node

treeNode *newNode(int item)

{

treeNode *temp = new treeNode;

temp->data = item;

temp->left = temp->right = NULL;

return temp;

}

/* A utility function to insert a new node with given key in BST */

treeNode* insert(treeNode* node, int key)

{

if (node == NULL) return newNode(key);

if (key < node->data)

node->left = insert(node->left, key);

else

node->right = insert(node->right, key);

return node;

}

// Driver program to test above function

int main()

{

int key = 65; //Key to be searched in BST

treeNode *root = NULL;

root = insert(root, 50);

insert(root, 30);

insert(root, 20);

insert(root, 40);

insert(root, 70);

insert(root, 60);

insert(root, 80);

treeNode* pre = NULL, *suc = NULL;

findPreSuc(root, pre, suc, key);

if (pre != NULL)

cout << "Predecessor is " << pre->data << endl;

else

cout << "No Predecessor";

if (suc != NULL)

cout << "Successor is " << suc->data;

else

cout << "No Successor";

return 0;

}

screenshots:

null