Sum of k smallest elements in BST | Java program to find Sum Of All Elements smaller than or equal to 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 ; 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 program to test above functions ; 20 / \ 8 22 / \ 4 12 / \ 10 14
import java . util . * ; class GFG { static class Node { int data ; Node left , right ; } ; static Node createNode ( int data ) { Node new_Node = new Node ( ) ; new_Node . left = null ; new_Node . right = null ; new_Node . data = data ; return new_Node ; } static Node insert ( Node root , int key ) { if ( root == null ) return createNode ( key ) ; if ( root . data > key ) root . left = insert ( root . left , key ) ; else if ( root . data < key ) root . right = insert ( root . right , key ) ; return root ; } static int count = 0 ; static int ksmallestElementSumRec ( Node root , int k ) { if ( root == null ) return 0 ; if ( count > k ) return 0 ; int res = ksmallestElementSumRec ( root . left , k ) ; if ( count >= k ) return res ; res += root . data ; count ++ ; if ( count >= k ) return res ; return res + ksmallestElementSumRec ( root . right , k ) ; } static int ksmallestElementSum ( Node root , int k ) { int res = ksmallestElementSumRec ( root , k ) ; return res ; } 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 ; int count = ksmallestElementSum ( root , k ) ; System . out . println ( count ) ; } }