Kth Smallest element in a Perfect Binary Search Tree | Python3 program to find K - th smallest element in a perfect BST ; A BST node ; 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 ; Recur down the left subtree for smaller values ; Recur down the right subtree for smaller values ; Return the ( unchanged ) node pointer ; FUnction to find Kth Smallest element in a perfect BST ; Find the median ( division operation is floored ) ; If the element is at the median ; Calculate the number of nodes in the right and left sub - trees ( division operation is floored ) ; If median is located higher ; If median is located lower ; Driver Code ; Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 / \ / \ / \ / \ 14 25 35 45 55 65 75 85 ; Function call
kth_smallest = 0 NEW_LINE class newNode : NEW_LINE INDENT def __init__ ( self , item ) : NEW_LINE INDENT self . key = item NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def insert ( node , key ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return newNode ( 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 def KSmallestPerfectBST ( root , k , treeSize ) : NEW_LINE INDENT global kth_smallest NEW_LINE if ( root == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT median_loc = ( treeSize // 2 ) + 1 NEW_LINE if ( k == median_loc ) : NEW_LINE INDENT kth_smallest = root . key NEW_LINE return True NEW_LINE DEDENT newTreeSize = treeSize // 2 NEW_LINE if ( k < median_loc ) : NEW_LINE INDENT return KSmallestPerfectBST ( root . left , k , newTreeSize ) NEW_LINE DEDENT newK = k - median_loc NEW_LINE return KSmallestPerfectBST ( root . right , newK , newTreeSize ) 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 insert ( root , 14 ) NEW_LINE insert ( root , 25 ) NEW_LINE insert ( root , 35 ) NEW_LINE insert ( root , 45 ) NEW_LINE insert ( root , 55 ) NEW_LINE insert ( root , 65 ) NEW_LINE insert ( root , 75 ) NEW_LINE insert ( root , 85 ) NEW_LINE n = 15 NEW_LINE k = 5 NEW_LINE if ( KSmallestPerfectBST ( root , k , n ) ) : NEW_LINE INDENT print ( kth_smallest , end = " ▁ " ) NEW_LINE DEDENT DEDENT