Sum of k smallest elements in BST | Python3 program to find Sum Of All Elements smaller than or equal to Kth Smallest Element In BST ; utility that allocates a newNode with the given key ; A utility function to insert a new Node with given key in BST and also maintain lcount , Sum ; If the tree is empty , return a new Node ; Otherwise , recur down the tree ; return the ( unchanged ) Node pointer ; function return sum of all element smaller than and equal to Kth smallest element ; Base cases ; Compute sum of elements in left subtree ; Add root 's data ; Add current Node ; If count is less than k , return right subtree Nodes ; Wrapper over ksmallestElementSumRec ( ) ; Driver Code ; 20 / \ 8 22 / \ 4 12 / \ 10 14
INT_MAX = 2147483647 NEW_LINE class createNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . data = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def insert ( root , key ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return createNode ( key ) NEW_LINE DEDENT if ( root . data > key ) : NEW_LINE INDENT root . left = insert ( root . left , key ) NEW_LINE DEDENT elif ( root . data < key ) : NEW_LINE INDENT root . right = insert ( root . right , key ) NEW_LINE DEDENT return root NEW_LINE DEDENT def ksmallestElementSumRec ( root , k , count ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( count [ 0 ] > k [ 0 ] ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT res = ksmallestElementSumRec ( root . left , k , count ) NEW_LINE if ( count [ 0 ] >= k [ 0 ] ) : NEW_LINE INDENT return res NEW_LINE DEDENT res += root . data NEW_LINE count [ 0 ] += 1 NEW_LINE if ( count [ 0 ] >= k [ 0 ] ) : NEW_LINE INDENT return res NEW_LINE DEDENT return res + ksmallestElementSumRec ( root . right , k , count ) NEW_LINE DEDENT def ksmallestElementSum ( root , k ) : NEW_LINE INDENT count = [ 0 ] NEW_LINE return ksmallestElementSumRec ( root , k , count ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE root = insert ( root , 20 ) NEW_LINE root = insert ( root , 8 ) NEW_LINE root = insert ( root , 4 ) NEW_LINE root = insert ( root , 12 ) NEW_LINE root = insert ( root , 10 ) NEW_LINE root = insert ( root , 14 ) NEW_LINE root = insert ( root , 22 ) NEW_LINE k = [ 3 ] NEW_LINE print ( ksmallestElementSum ( root , k ) ) NEW_LINE DEDENT