### 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