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.

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro