How to implement decrease key or change key in Binary Search Tree ? | JavaScript program to demonstrate decrease key operation on binary search tree ; A utility function to create a new BST node ; A utility function to do inorder traversal of BST ; A utility function to insert a new node with given key in BST ; If the tree is empty , return a new node ; Otherwise , recur down the tree ; return the ( unchanged ) node pointer ; Given a non - empty binary search tree , return the node with minimum key value found in that tree . Note that the entire tree does not need to be searched . ; loop down to find the leftmost leaf ; Given a binary search tree and a key , this function deletes the key and returns the new root ; base case ; If the key to be deleted is smaller than the root 's key,  then it lies in left subtree ; If the key to be deleted is greater than the root 's key,  then it lies in right subtree ; if key is same as root 's  key, then This is the node  to be deleted ; node with only one child or no child ; node with two children : Get the inorder successor ( smallest in the right subtree ) ; Copy the inorder successor 's  content to this node ; Delete the inorder successor ; Function to decrease a key value in Binary Search Tree ; First delete old key value ; Then insert new key value ; Return new root ; Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 ; BST is modified to 50 / \ 30 70 / / \ 20 60 80 / 10
class node { constructor ( ) { this . key = 0 ; this . left = null ; this . right = null ; } } var root = null ; function newNode ( item ) { var temp = new node ( ) ; temp . key = item ; temp . left = null ; temp . right = null ; return temp ; } function inorder ( root ) { if ( root != null ) { inorder ( root . left ) ; document . write ( root . key + " " ) ; inorder ( root . right ) ; } } 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 ; } function minValueNode ( Node ) { var current = Node ; while ( current . left != null ) current = current . left ; return current ; } function deleteNode ( root , key ) { if ( root == null ) return root ; if ( key < root . key ) root . left = deleteNode ( root . left , key ) ; else if ( key > root . key ) root . right = deleteNode ( root . right , key ) ; else { if ( root . left == null ) { temp = root . right ; return temp ; } else if ( root . right == null ) { temp = root . left ; return temp ; } var temp = minValueNode ( root . right ) ; root . key = temp . key ; root . right = deleteNode ( root . right , temp . key ) ; } return root ; } function changeKey ( root , oldVal , newVal ) { root = deleteNode ( root , oldVal ) ; root = insert ( root , newVal ) ; return root ; } root = insert ( root , 50 ) ; root = insert ( root , 30 ) ; root = insert ( root , 20 ) ; root = insert ( root , 40 ) ; root = insert ( root , 70 ) ; root = insert ( root , 60 ) ; root = insert ( root , 80 ) ; document . write ( " " ) ; inorder ( root ) ; root = changeKey ( root , 40 , 10 ) ; document . write ( " " ) ; inorder ( root ) ;