Sum of k smallest elements in BST | Java 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
import java . util . * ; class GFG { static class Node { int data ; int lCount ; int Sum ; Node left ; Node right ; } ; static 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 ; } static 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 ; } static int temp_sum ; static void ksmallestElementSumRec ( Node root , int k ) { 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 ) ; } else ksmallestElementSumRec ( root . left , k ) ; } static void ksmallestElementSum ( Node root , int k ) { temp_sum = 0 ; ksmallestElementSumRec ( root , k ) ; } public static void main ( String [ ] args ) { 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 ; ksmallestElementSum ( root , k ) ; System . out . println ( temp_sum ) ; } }