Sum of k smallest elements in BST | C ++ program to find Sum Of All Elements smaller than or equal t Kth Smallest Element In BST ; Binary tree Node ; 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 program to test above functions ; 20 / \ 8 22 / \ 4 12 / \ 10 14
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; int lCount ; int Sum ; Node * left ; Node * right ; } ; struct Node * createNode ( int data ) { Node * new_Node = new Node ; new_Node -> left = NULL ; new_Node -> right = NULL ; new_Node -> data = data ; new_Node -> lCount = 0 ; new_Node -> Sum = 0 ; return new_Node ; } struct Node * insert ( Node * root , int key ) { if ( root == NULL ) return createNode ( key ) ; if ( root -> data > key ) { root -> lCount ++ ; root -> Sum += key ; root -> left = insert ( root -> left , key ) ; } else if ( root -> data < key ) root -> right = insert ( root -> right , key ) ; return root ; } void ksmallestElementSumRec ( Node * root , int k , int & temp_sum ) { if ( root == NULL ) return ; if ( ( root -> lCount + 1 ) == k ) { temp_sum += root -> data + root -> Sum ; return ; } else if ( k > root -> lCount ) { temp_sum += root -> data + root -> Sum ; k = k - ( root -> lCount + 1 ) ; ksmallestElementSumRec ( root -> right , k , temp_sum ) ; } else ksmallestElementSumRec ( root -> left , k , temp_sum ) ; } int ksmallestElementSum ( struct Node * root , int k ) { int sum = 0 ; ksmallestElementSumRec ( root , k , sum ) ; return sum ; } int main ( ) { Node * root = NULL ; root = insert ( root , 20 ) ; root = insert ( root , 8 ) ; root = insert ( root , 4 ) ; root = insert ( root , 12 ) ; root = insert ( root , 10 ) ; root = insert ( root , 14 ) ; root = insert ( root , 22 ) ; int k = 3 ; cout << ksmallestElementSum ( root , k ) << endl ; return 0 ; }