Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples 
2.
Naive Approach
2.1.
Algorithm to print the sum of k smallest elements in BST
2.2.
Implementation
2.2.1.
Time Complexity 
2.2.2.
Space Complexity 
3.
Optimal Approach
3.1.
Algorithm to print the sum of k smallest elements in BST
3.2.
Implementation
3.2.1.
Time Complexity 
3.2.2.
Space Complexity 
4.
Frequently Asked Questions
4.1.
What is the purpose of a tree data structure? 
4.2.
What is a kth smallest element?
4.3.
What is Inorder in Data Structures?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Print the sum of k smallest elements in BST

Author Sagar Mishra
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

A BST (Binary Search Tree) is a tree in which the key of the nodes of the left sub-tree has a lower value than its parent node's key. And the key of the right sub-tree is greater than or equal to the key of its parent (root) node.

A binary Search Tree is a collection of nodes that are arranged in such a way that they retain BST properties.

Sum of K Smallest elements in BST

In this article, we will solve a question based on the topic of BST. The question says to print the sum of k smallest elements in BST.

Problem Statement

In this question, the goal is to determine the sum of all elements that are less than or equal to Kth's smallest element.

Let's take some examples of the given problem statement.

Sample Examples 

Example 1:

Input

k = 3

Example1

Output: 

152

 

Example 2:

Input:

k = 3

Input2

Output:

38

Naive Approach

The most basic pattern search algorithm is known as naive pattern searching. It checks that each character in the primary string matches the pattern. For a specific type of pattern question, this algorithm is useful. No pre-processing steps are required in this approach.

Let's now discuss the algorithm for the above approach.

Algorithm to print the sum of k smallest elements in BST

🚩 Perform the Inorder traversal to the given BST.

🚩 Count the number of elements visited.

🚩 Add all the elements to an integer variable.

🚩 Return the integer variable when the count of the element is equal to k.

Implementation

C++

#include <bits/stdc++.h>
using namespace std;


struct Node
{
  int data;
  Node *left, *right;
};


struct Node *
createNode (int data)
{
  Node *new_Node = new Node;
  new_Node->left = NULL;
  new_Node->right = NULL;
  new_Node->data = data;
  return new_Node;
}


struct 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;
}


int ksmallestSum (Node * root, int k, int &count)
{


  if (root == NULL)
    return 0;
  if (count > k)
    return 0;


  int res = ksmallestSum (root->left, k, count);
  if (count >= k)
    return res;


  res += root->data;



  count++;
  if (count == k)
    return res;


  return res + ksmallestSum (root->right, k, count);
}


int ksmallestSum (struct Node *root, int k)
{
  int count = 0;
  return ksmallestSum (root, k, count);
}


int main ()
{



  Node *root = NULL;
  root = insert (root, 49);
  root = insert (root, 46);
  root = insert (root, 44);
  root = insert (root, 47);
  root = insert (root, 70);
  root = insert (root, 69);
  root = insert (root, 80);


  int k = 3;
  cout << "Sum of k smallest elements is " << ksmallestSum (root, k) << endl;
  return 0;
}

 

Output:

Sum of k smallest elements is 137

Time Complexity 

The time complexity of the above code is O(N) (where N is the number of elements in the tree). We have gone through the complete tree to perform the Inorder traversal.

Space Complexity 

The space complexity of the above code is O(1). It is O(1) because the integer variable takes one extra space in the memory.

Read More - Time Complexity of Sorting Algorithms

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimal Approach

In the Optimal Approach, we will use the Augmented tree data structure to solve the question "Print the sum of k smallest elements in BST." Let's now discuss the algorithm for the Optimal Approach.

Algorithm to print the sum of k smallest elements in BST

📣 When adding a node to this tree, if the key value is less than the value of the existing node, the current node's value is added to the key value. And the node's lcount is raised by 1.

📣 Go to a similar binary tree if the key value is greater than the current node.

📣 Apply the above procedure to every node that gets in your way until you reach the insertion location.

Implementation

C++

#include <bits/stdc++.h>
using namespace std;


/* Binary tree Node */
struct Node
{
  int data;
  int lCount;
  int Sum;
  Node *left;
  Node *right;
};


//utility function new Node of BST 
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)
{
  // return a new Node, in case the tree is empty,  
  if (root == NULL)
    return createNode (key);


  // Otherwise, recur down the tree 
  if (root->data > key)
    {
      // increment lCount of current Node 
      root->lCount++;


      // increment current Node sum by adding 
      // key into it 
      root->Sum += key;


      root->left = insert (root->left, key);
    }
  else if (root->data < key)
    root->right = insert (root->right, key);


  // return the (unchanged) Node pointer 
  return root;
}


// function return sum of all elements smaller than and equal 
// to Kth smallest element 
void ksmallestSum (Node * root, int k, int &temp_sum)
{
  if (root == NULL)
    return;


  // break the function if we fount k smallest element.
  if ((root->lCount + 1) == k)
    {
      temp_sum += root->data + root->Sum;
      return;
    }


  else if (k > root->lCount)
    {
      // store sum of all elements smaller than the current root ; 
      temp_sum += root->data + root->Sum;


      // decremented k and call right sub-tree 
      k = k - (root->lCount + 1);
      ksmallestSum (root->right, k, temp_sum);
    }
  else // call left sub-tree 
    ksmallestSum (root->left, k, temp_sum);
}


// Wrapper over ksmallestSum() 
int ksmallestElementSum (struct Node *root, int k)
{
  int sum = 0;
  ksmallestSum (root, k, sum);
  return sum;
}


/* Driver program to test above functions */
int main ()
{
  Node *root = NULL;
  root = insert (root, 23);
  root = insert (root, 11);
  root = insert (root, 7);
  root = insert (root, 15);
  root = insert (root, 13);
  root = insert (root, 17);
  root = insert (root, 25);


  int k = 3;
  cout << "Sum of k smallest is " << ksmallestElementSum (root, k) << endl;
  return 0;
}

 

Output:

Sum of k smallest is 31

Time Complexity 

The time complexity of the question "Print the sum of k smallest elements in BST" is O(log N) because of the recurring function of the tree traversal. Here N is the number of elements in the tree.

Space Complexity 

The space complexity of the question "Print the sum of k smallest elements in BST" is O(h). Here, h is the constant in the given binary tree.

Check out this problem - Pair Sum In Array.

Frequently Asked Questions

What is the purpose of a tree data structure? 

A tree known as a binary search tree enables quick searches, data insertion, and deletion. Finding the thing closest to you is aided by this as well. Arrays are used to build priority queues in the heap tree data structure.

What is a kth smallest element?

The kth smallest element is the lowest n that can exist while ensuring that the array has at least k elements. As stated, if array A was sorted, then A[k - 1] (The arrays are 0 based, whereas k is 1 based).

What is Inorder in Data Structures?

An In-order traversal of a tree first visits the left subtree, then the root node, and finally, the right subtree of the binary tree. It is used to clarify the binary tree's increasing order of nodes.

Conclusion

We have discussed the topic of "Print the sum of k smallest elements in BST." In detail, we have seen the examples, problem statement, approach, algorithm, and implementation. 

We hope this blog has helped you enhance your knowledge of the "Print the sum of k smallest elements in BST." If you want to learn more, check out our articles Add all greater values to every node in a given BSTMother vertex in a GraphAlternative sorting, and many more on our platform Coding Ninjas Studio.

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning!

Previous article
Find if there is a Triplet in a Balanced BST that Adds to 0
Next article
Count Pairs From Two BSTs Whose Sum is Equal to a Given Value
Live masterclass