Sum of k smallest elements in BST | utility function new Node of BST ; 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 ; increment lCount of current Node ; increment current Node sum by adding key into it ; return the ( unchanged ) Node pointer ; function return sum of all element smaller than and equal to Kth smallest element ; if we fount k smallest element then break the function ; store sum of all element smaller than current root ; ; decremented k and call right sub - tree ; call left sub - tree ; Wrapper over ksmallestElementSumRec ( ) ; Driver Code ; 20 / \ 8 22 / \ 4 12 / \ 10 14
class createNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . lCount = 0 NEW_LINE self . Sum = 0 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 . lCount += 1 NEW_LINE root . Sum += key NEW_LINE 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 , temp_sum ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT return NEW_LINE DEDENT if ( root . lCount + 1 ) == k : NEW_LINE INDENT temp_sum [ 0 ] += root . data + root . Sum NEW_LINE return NEW_LINE DEDENT elif k > root . lCount : NEW_LINE INDENT temp_sum [ 0 ] += root . data + root . Sum NEW_LINE k = k - ( root . lCount + 1 ) NEW_LINE ksmallestElementSumRec ( root . right , k , temp_sum ) NEW_LINE DEDENT else : NEW_LINE INDENT ksmallestElementSumRec ( root . left , k , temp_sum ) NEW_LINE DEDENT DEDENT def ksmallestElementSum ( root , k ) : NEW_LINE INDENT Sum = [ 0 ] NEW_LINE ksmallestElementSumRec ( root , k , Sum ) NEW_LINE return Sum [ 0 ] 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