Inorder Successor in Binary Search Tree | A binary tree node ; * Given a binary search tree and a number , inserts a new node with the given * number in the correct place in the tree . Returns the new root pointer which * the caller should then use ( the standard trick to afunction using reference * parameters ) . ; * 1. If the tree is empty , return a new , single node ; 2. Otherwise , recur down the tree ; return the ( unchanged ) node pointer ; step 1 of the above algorithm ; step 2 of the above algorithm ; * Given a non - empty binary search tree , return the minimum data value found in * that tree . Note that the entire tree does not need to be searched . ; loop down to find the leftmost leaf ; Driver program to test above functions
class Node { constructor ( val ) { this . data = val ; this . left = null ; this . right = null ; this . parent = null ; } } var head ; function insert ( node , data ) { if ( node == null ) { return ( new Node ( data ) ) ; } else { var temp = null ; if ( data <= node . data ) { temp = insert ( node . left , data ) ; node . left = temp ; temp . parent = node ; } else { temp = insert ( node . right , data ) ; node . right = temp ; temp . parent = node ; } return node ; } } function inOrderSuccessor ( root , n ) { if ( n . right != null ) { return minValue ( n . right ) ; } var p = n . parent ; while ( p != null && n == p . right ) { n = p ; p = p . parent ; } return p ; } function minValue ( node ) { var current = node ; while ( current . left != null ) { current = current . left ; } return current ; } var root = null , temp = null , suc = null , min = null ; root = insert ( root , 20 ) ; root = insert ( root , 8 ) ; root = insert ( root , 22 ) ; root = insert ( root , 4 ) ; root = insert ( root , 12 ) ; root = insert ( root , 10 ) ; root = insert ( root , 14 ) ; temp = root . left . right . right ; suc = inOrderSuccessor ( root , temp ) ; if ( suc != null ) { document . write ( " " + temp . data + " " + suc . data ) ; } else { document . write ( " " ) ; }