K 'th smallest element in BST using O(1) Extra Space | A BST node ; A function to find ; Count to iterate over elements till we get the kth smallest number ; store the Kth smallest ; to store the current node ; Like Morris traversal if current does not have left child rather than printing as we did in inorder , we will just increment the count as the number will be in an increasing order ; if count is equal to K then we found the kth smallest , so store it in ksmall ; go to current 's right child ; we create links to Inorder Successor and count using these links ; building links ; link made to Inorder Successor ; While breaking the links in so made temporary threaded tree we will check for the K smallest condition ; Revert the changes made in if part ( break link from the Inorder Successor ) ; If count is equal to K then we found the kth smallest and so store it in ksmall ; return the found value ; A utility function to create a new BST node ; 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 ; Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80
class Node { constructor ( ) { this . key = 0 ; this . left = null ; this . right = null ; } } function KSmallestUsingMorris ( root , k ) { var count = 0 ; var ksmall = Number . MIN_VALUE ; var curr = root ; while ( curr != null ) { if ( curr . left == null ) { count ++ ; if ( count == k ) ksmall = curr . key ; curr = curr . right ; } else { var pre = curr . left ; while ( pre . right != null && pre . right != curr ) pre = pre . right ; if ( pre . right == null ) { pre . right = curr ; curr = curr . left ; } else { pre . right = null ; count ++ ; if ( count == k ) ksmall = curr . key ; curr = curr . right ; } } } return ksmall ; } function newNode ( item ) { var temp = new Node ( ) ; temp . key = item ; temp . left = null ; 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 if ( key > node . key ) node . right = insert ( node . right , key ) ; return node ; } 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 ) ; for ( k = 1 ; k <= 7 ; k ++ ) document . write ( KSmallestUsingMorris ( root , k ) + " " ) ;