Find k | A BST node ; Recursive function to insert an key into BST ; If a node is inserted in left subtree , then lCount of this node is increased . For simplicity , we are assuming that all keys ( tried to be inserted ) are distinct . ; Function to find k 'th largest element in BST. Here count denotes the number of nodes processed so far ; Base case ; Else search in right subtree ; Driver code
class newNode : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . data = x NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE self . lCount = 0 NEW_LINE DEDENT DEDENT def insert ( root , x ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return newNode ( x ) NEW_LINE DEDENT if ( x < root . data ) : NEW_LINE INDENT root . left = insert ( root . left , x ) NEW_LINE root . lCount += 1 NEW_LINE DEDENT elif ( x > root . data ) : NEW_LINE INDENT root . right = insert ( root . right , x ) ; NEW_LINE DEDENT return root NEW_LINE DEDENT def kthSmallest ( root , k ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return None NEW_LINE DEDENT count = root . lCount + 1 NEW_LINE if ( count == k ) : NEW_LINE INDENT return root NEW_LINE DEDENT if ( count > k ) : NEW_LINE INDENT return kthSmallest ( root . left , k ) NEW_LINE DEDENT return kthSmallest ( root . right , k - count ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE keys = [ 20 , 8 , 22 , 4 , 12 , 10 , 14 ] NEW_LINE for x in keys : NEW_LINE INDENT root = insert ( root , x ) NEW_LINE DEDENT k = 4 NEW_LINE res = kthSmallest ( root , k ) NEW_LINE if ( res == None ) : NEW_LINE INDENT print ( " There ▁ are ▁ less ▁ than ▁ k ▁ nodes ▁ in ▁ the ▁ BST " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " K - th ▁ Smallest ▁ Element ▁ is " , res . data ) NEW_LINE DEDENT DEDENT