Sum of K smallest Elements in BST Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/sum-of-k-smallest-elements-in-bst3029/1

Solution:

class Tree {

    public static void fun(Node root,ArrayList<Integer>aa){

        if(root==null){

            return ;

        }

        else{

            fun(root.left,aa);

            aa.add(root.data);

            fun(root.right,aa);

        }

    }

    int sum(Node root, int k) { 

        ArrayList<Integer>aa=new ArrayList<Integer>();

        fun(root,aa);

        int sum=0;

        for(int i=0;i<k;i++){

            sum=sum+aa.get(i);

        }

        return sum;

        

    } 

}

Time Complexity: O(N)[Whole tree traversal][GFG Time:0.13]

Space Complexity: O[N][A tree of N nodes is given]

Auxiliary Space: O[N][An ArrayList storing N nodes data]

Total Test Cases:112

Approach Used:

Here we need to find out the sum of k smallest elements, so for that, if we get the list sorted in ascending order of all the elements then easily we can find out the sum of all elements till the count of elements is less than k.

1. So to find out the sorted list we know that in-order BST is sorted(in ascending order) and storing all node's data in an ArrayList will solve our objective.

2. So we travel the tree and find out the inorder traversal of the tree and store it in ArrayList aa.

3. Later we traverse the ArrayList aa till k and simultaneously do the sum of elements.

4. Return this sum.

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"