Inorder predecessor and successor for a given key in BST | Iterative Approach | C ++ program to find predecessor and successor in a BST ; BST Node ; Function that finds predecessor and successor of key in BST . ; Search for given key in BST . ; If root is given key . ; the minimum value in right subtree is predecessor . ; the maximum value in left subtree is successor . ; If key is greater than root , then key lies in right subtree . Root could be predecessor if left subtree of key is null . ; If key is smaller than root , then key lies in left subtree . Root could be successor if right subtree of key is null . ; A utility function to create a new BST node ; A utility function to insert a new node with given key in BST ; Driver program to test above function ; Key to be searched in BST ; Let us create following BST 50 / \ / \ 30 70 / \ / \ / \ / \ 20 40 60 80
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; struct Node * left , * right ; } ; void findPreSuc ( Node * root , Node * & pre , Node * & suc , int key ) { if ( root == NULL ) return ; while ( root != NULL ) { if ( root -> key == key ) { if ( root -> right ) { suc = root -> right ; while ( suc -> left ) suc = suc -> left ; } if ( root -> left ) { pre = root -> left ; while ( pre -> right ) pre = pre -> right ; } return ; } else if ( root -> key < key ) { pre = root ; root = root -> right ; } else { suc = root ; root = root -> left ; } } } Node * newNode ( int item ) { Node * temp = new Node ; temp -> key = item ; temp -> left = temp -> right = NULL ; return temp ; } 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 ; 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 << " - 1" ; if ( suc != NULL ) cout << " Successor ▁ is ▁ " << suc -> key ; else cout << " - 1" ; return 0 ; }