C++ program to find inorder predecessor and successor for a given key in binary search tree without recursion
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node *left, *right;
};
// Function that finds predecessor and successor of key in BST.
void PredSucc(Node* root, Node*& pre, Node*& suc, int key)
{
if (root == NULL)
return;
// Searching for given key in BST.
while (root != NULL) {
// If root is given key.
if (root->key == key) {
// the min value in right subtree is predecessor.
if (root->right) {
suc = root->right;
while (suc->left)
suc = suc->left;
}
// the max value in left subtree is successor.
if (root->left) {
pre = root->left;
while (pre->right)
pre = pre->right;
}
return;
}
// If key is greater than root, then key lies in right subtree.
else if (root->key < key) {
pre = root;
root = root->right;
}
// If key is smaller than root, then key lies in left subtree.
else {
suc = root;
root = root->left;
}
}
}
// function to create a new BST node
Node* newNode(int item)
{
Node* temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// 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()
{
// Key to be searched in BST
int key = 45;
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;
PredSucc(root, pre, suc, key);
if (pre != NULL)
cout << "Predecessor" << " of "<<key<<" is " << pre->key<<endl;
else
cout << "-1";
if (suc != NULL)
cout << "Successor" << " of "<<key<<" is " << suc->key<<endl;
else
cout << "-1";
return 0;
}
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80
*/
// OUTPUT ::
// Predecessor of 45 is 40
//Successor of 45 is 50
Comments