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 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 ; Driver Code ; Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . key = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def KSmallestUsingMorris ( root , k ) : NEW_LINE INDENT count = 0 NEW_LINE ksmall = - 9999999999 NEW_LINE curr = root NEW_LINE while curr != None : NEW_LINE INDENT if curr . left == None : NEW_LINE INDENT count += 1 NEW_LINE if count == k : NEW_LINE INDENT ksmall = curr . key NEW_LINE DEDENT curr = curr . right NEW_LINE DEDENT else : NEW_LINE INDENT pre = curr . left NEW_LINE while ( pre . right != None and pre . right != curr ) : NEW_LINE INDENT pre = pre . right NEW_LINE DEDENT if pre . right == None : NEW_LINE INDENT pre . right = curr NEW_LINE curr = curr . left NEW_LINE DEDENT else : NEW_LINE INDENT pre . right = None NEW_LINE count += 1 NEW_LINE if count == k : NEW_LINE INDENT ksmall = curr . key NEW_LINE DEDENT curr = curr . right NEW_LINE DEDENT DEDENT DEDENT return ksmall NEW_LINE DEDENT def insert ( node , key ) : NEW_LINE INDENT if node == None : NEW_LINE INDENT return Node ( key ) NEW_LINE DEDENT if key < node . key : NEW_LINE INDENT node . left = insert ( node . left , key ) NEW_LINE DEDENT elif key > node . key : NEW_LINE INDENT node . right = insert ( node . right , key ) NEW_LINE DEDENT return node NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE root = insert ( root , 50 ) NEW_LINE insert ( root , 30 ) NEW_LINE insert ( root , 20 ) NEW_LINE insert ( root , 40 ) NEW_LINE insert ( root , 70 ) NEW_LINE insert ( root , 60 ) NEW_LINE insert ( root , 80 ) NEW_LINE for k in range ( 1 , 8 ) : NEW_LINE INDENT print ( KSmallestUsingMorris ( root , k ) , end = " ▁ " ) NEW_LINE DEDENT DEDENT