 ### C++ program to find inorder predecessor and successor for a given key in binary search tree with recursion

Objective: %u2013 Finding inorder predecessor and successor for a given key in binary search tree with recursion

What is Predecessor and Successor :

When you do the inorder traversal of a binary tree, the neighbors of given node are called Predecessor(the node lies behind of given node) and Successor (the node lies ahead of given node).

Example: Approach:

Say you have to find the inorder predecessor and successor node 15.

• First compare the 15 with root (25 here).
• 25>15 => successor = 25, make recursive call to root.left.(Why do we do it , is explained at step 3).
• New root which is = 15, now stop making recursive calls.
• Now successor will be the left most node in right subtree of which has the root 18 here. So the left most element and successor will be 19. (What if 15 doesn%u2019t have a right subtree, then successor of 15 will be the parent of it, and that is why we set parent as successor in step1).
• Now predecessor will be the right most node in left subtree which has the root 10 here. but 10 doesn%u2019t have right child.
• For the same reason when node<root then make predecessor = root and make a recursive call to the root.right.

Algorithm:
```Input: root node, key
output: predecessor node, successor node

1. If root is NULL
then return
2. if key is found then
a. If its left subtree is not null
Then predecessor will be the right most
child of left subtree or left child itself.
b. If its right subtree is not null
The successor will be the left most child
of right subtree or right child itself.
return
3. If key is smaller then root node
set the successor as root
search recursively into left subtree
else
set the predecessor as root
search recursively into right subtree```

Code(C++):

// C++ program to find predecessor and successor in a BST
#include <iostream>
using namespace std;

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

// This function finds predecessor and successor of key in BST.
// It sets pre and suc as predecessor and successor respectively
void findPreSuc(Node* root, Node*& pre, Node*& suc, int key)
{
// Base case
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 ;
}

// the minimum value in right subtree is successor
if (root->right != NULL)
{
Node* tmp = root->right ;
while (tmp->left)
tmp = tmp->left ;
suc = tmp ;
}
return ;
}

// If key is smaller than root's key, go to left subtree
if (root->key > 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
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;
}

// Driver program to test above function
int main()
{
int key = 65; //Key to be searched in BST

/* Let us create following BST
50
/     \
30     70
/ \ / \
20 40 60 80 */
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
cout << "No Predecessor";

if (suc != NULL)
cout << "Successor is " << suc->key;
else
cout << "No Successor";
return 0;
}

Output:
```Predecessor is 60
Successor is 70##An article by Yashwanth Gudigamolla``` #### More Articles of yashwanth gudigamolla:

Name Views Likes
Python SciPy stats.skew() function 1588 17
Python Scipy Stats 1167 14
Python SciPy stats beta() function 2029 14
Python Scipy Special (List of Different Functions) 1548 15
Python SciPy Integration 1409 12
Python Scipy Fourier Transforms(scipy.fftpack) 1462 17
Python Scipy linalg 1316 13
Python SciPy stats.expon() function 2287 17
Python SciPy stats.chi() function 993 24
Python Scipy Multidimentional image processing (scipy.ndimage) 1618 26
SciPy - ODR 1485 23
Python SciPy stats.cosine() function 958 14
Python SciPy stats.trim1() function 1051 11
Python SciPy stats.tvar() function 1107 16
Python SciPy stats.tvar() function 1046 23
SciPy - Basic Functionality 1152 27
Python SciPy stats.betaprime() function 1006 13
Python Scipy CSGraph 1204 19
Python Scipy File Input and Output (IO) 1616 20
Python Scipy Optimize 1444 23
Python Scipy Special package (scipy.special) 1107 25
Python SciPy stats.tsem() function 949 12
Python SciPy stats.variation() function 1386 16
Python SciPy stats.tsem() function 998 14
SciPy - Spatial 1179 25
Python program to insert an element into binary search tree 9696 29
Python SciPy stats.chi2() function 1905 18
Python SciPy Interpolation 6649 21
C++ program to find inorder predecessor and successor for a given key in binary search tree with recursion 2478 15
python program to check if two trees are identical using recursion 1192 12
Python SciPy constants 2014 18
Python SciPy stats.sem() function 1338 22
Python Scipy Introduction 1684 26
Python SciPy stats alpha() function 1170 23
SciPy - Cluster 1285 20