Inorder predecessor and successor for a given key in BST | Iterative Approach | 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 ; Key to be searched in BST ; Let us create following BST 50 / \ / \ 30 70 / \ / \ / \ / \ 20 40 60 80
class Node { constructor ( val ) { this . key = val ; this . left = null ; this . right = null ; } } var pre ; var suc ; function findPreSuc ( root , 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 ; } } } function newNode ( item ) { var temp = new Node ( ) ; temp . key = item ; temp . left = temp . right = null ; return temp ; } function insert ( node , 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 ; } var key = 65 ; var 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 ) document . write ( " " + pre . key + " " ) ; else document . write ( " " ) ; if ( suc != null ) document . write ( " " + suc . key ) ; else document . write ( " " ) ;