Inorder predecessor and successor for a given key in BST | Iterative Approach | Java 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 successor . ; the maximum value in left subtree is predecessor . ; 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 Code ; Key to be searched in BST ; Let us create following BST 50 / \ / \ 30 70 / \ / \ / \ / \ 20 40 60 80
import java . util . * ; class GFG { static class Node { int key ; Node left , right ; } ; static Node pre ; static Node suc ; static void findPreSuc ( Node root , int key ) { if ( root == null ) return ; while ( root != null ) { if ( root . key == key ) { if ( root . right != null ) { suc = root . right ; while ( suc . left != null ) suc = suc . left ; } if ( root . left != null ) { pre = root . left ; while ( pre . right != null ) pre = pre . right ; } return ; } else if ( root . key < key ) { pre = root ; root = root . right ; } else { suc = root ; root = root . left ; } } } static Node newNode ( int item ) { Node temp = new Node ( ) ; temp . key = item ; temp . left = temp . right = null ; return temp ; } static 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 ; } public static void main ( String [ ] args ) { 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 ) ; findPreSuc ( root , key ) ; if ( pre != null ) System . out . println ( " Predecessor ▁ is ▁ " + pre . key ) ; else System . out . print ( " - 1" ) ; if ( suc != null ) System . out . print ( " Successor ▁ is ▁ " + suc . key ) ; else System . out . print ( " - 1" ) ; } }