# Sum of k smallest elements in BST

QUESTION

Given Binary Search Tree. The task is to find sum of all elements smaller than and equal to Kth smallest element.\n\nExamples:\n\nInput : K = 3\n 8\n / \\\n 7 10\n / / \\\n 2 9 13\nOutput : 17\nExplanation : Kth smallest element is 8 so sum of all\n element smaller then or equal to 8 are\n 2 + 7 + 8\n\nInput : K = 5\n 8\n / \\\n 5 11\n / \\\n 2 7\n \\\n 3\nOutput : 25.

``````#include<iostream>
#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 ksmallestElementSumRec(Node *root, int k, int &count)
{

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

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

res += root->data;

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

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

int ksmallestElementSum(struct Node *root, int k)
{
int count = 0;
ksmallestElementSumRec(root, k, count);
}

int main()
{

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;
cout <<  ksmallestElementSum(root, k) <<endl;
return 0;
}``````