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.

ANSWER

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