K 'th Largest element in BST using constant extra space | helper function to create a new Node ; count variable to keep count of visited Nodes ; if right child is None ; first increment count and check if count = k ; otherwise move to the left child ; find inorder successor of current Node ; set left child of successor to the current Node ; move current to its right ; restoring the tree back to original binary search tree removing threaded links ; move current to its left child ; Driver Code ; Constructed binary tree is 4 / \ 2 7 / \ / \ 1 3 6 10
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . right = self . left = None NEW_LINE DEDENT DEDENT def KthLargestUsingMorrisTraversal ( root , k ) : NEW_LINE INDENT curr = root NEW_LINE Klargest = None NEW_LINE count = 0 NEW_LINE while ( curr != None ) : NEW_LINE INDENT if ( curr . right == None ) : NEW_LINE INDENT count += 1 NEW_LINE if ( count == k ) : NEW_LINE INDENT Klargest = curr NEW_LINE DEDENT curr = curr . left NEW_LINE DEDENT else : NEW_LINE INDENT succ = curr . right NEW_LINE while ( succ . left != None and succ . left != curr ) : NEW_LINE INDENT succ = succ . left NEW_LINE DEDENT if ( succ . left == None ) : NEW_LINE INDENT succ . left = curr NEW_LINE curr = curr . right NEW_LINE DEDENT else : NEW_LINE INDENT succ . left = None NEW_LINE count += 1 NEW_LINE if ( count == k ) : NEW_LINE INDENT Klargest = curr NEW_LINE DEDENT curr = curr . left NEW_LINE DEDENT DEDENT DEDENT return Klargest NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 4 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 7 ) NEW_LINE root . left . left = newNode ( 1 ) NEW_LINE root . left . right = newNode ( 3 ) NEW_LINE root . right . left = newNode ( 6 ) NEW_LINE root . right . right = newNode ( 10 ) NEW_LINE print ( " Finding ▁ K - th ▁ largest ▁ Node ▁ in ▁ BST ▁ : ▁ " , KthLargestUsingMorrisTraversal ( root , 2 ) . data ) NEW_LINE DEDENT