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.
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

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.

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.

Example 1:

Input

k = 3

Output:

152

Example 2:

Input:

k = 3

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.

đźš© 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.

### 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!

Live masterclass