# Sum of k smallest elements in BST

Here given code implementation process.

``````//C Program
//Sum of k smallest elements in BST
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
int data;
struct Node *left,*right;
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
//Create a dynamic node of binary search tree
struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));

if(new_node!=NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL;//Initially node right-pointer is NULL

if(*root == NULL)
{
//When adds a first node in binary tree
*root = new_node;
}
else
{
struct Node *find = *root;
//iterate binary tree and add new node to proper position
while(find != NULL)
{
if(find -> data > data)
{
if(find->left==NULL)
{
find->left = new_node;
break;
}
else
{ //visit left sub-tree
find = find->left;
}
}
else
{
if(find->right == NULL)
{
find->right = new_node;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}

}

void k_smallest(struct Node*root,int *result,int *counter,int k)
{
if(root != NULL && *counter < k)
{

k_smallest(root->left,result,counter,k);
if(*counter<k)
{
(*result)  =(*result) + root->data;
(*counter)++;
}
k_smallest(root->right,result,counter,k);
}
}
void smallest_sum(struct Node*root,int k)
{
if(k<=0)
{
return;
}
if(root != NULL)
{
int result=0,counter=0;
k_smallest(root,&result,&counter,k);
printf("%d\n",result );
}

}

int main()
{

struct Node*root = NULL;

//Add nodes in binary search tree
/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2   7        12

*/

smallest_sum(root,3);
smallest_sum(root,5);
return 0;
}``````

#### Output

``````0
7
``````
``````//C++ Program
//Sum of k smallest elements in BST
#include <iostream>
using namespace std;

//ure of Binary Search Tree node
struct Node
{
int data;
Node *left,*right;
};

class BST
{

public:
Node*root;
BST();
//public methods
void k_smallest( Node*root,int *result,int *counter,int k);
void smallest_sum(int k);
};
BST::BST()
{
root=NULL;
}
//Adding a new node in binary search tree
{
//Create a dynamic node of binary search tree
Node *new_node = new Node();

if(new_node!=NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL;//Initially node right-pointer is NULL

if(root == NULL)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
Node *find = root;

//add new node to proper position
while(find != NULL)
{
if(find -> data >= data)
{
if(find->left==NULL)
{
find->left = new_node;
break;
}
else
{
//visit left sub-tree
find = find->left;
}
}
else
{
if(find->right == NULL)
{
find->right = new_node;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}
else
{
cout<<("Memory Overflow\n");
}
}

void BST:: k_smallest( Node*root,int *result,int *counter,int k)
{
if(root != NULL && *counter < k)
{

k_smallest(root->left,result,counter,k);
if(*counter<k)
{
(*result)  =(*result) + root->data;
(*counter)++;
}
k_smallest(root->right,result,counter,k);
}
}
void BST:: smallest_sum(int k)
{
if(k<=0)
{
return;
}
if(root != NULL)
{
int result=0,counter=0;
k_smallest(root,&result,&counter,k);
cout<<"  "<<result<<endl;
}

}

int main()
{
//Create object
BST obj;

//Add nodes in binary search tree
/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2   7        12
*/

obj.smallest_sum(3);
obj.smallest_sum(5);

return 0;
}``````

#### Output

``````  0
7
``````
``````//Java program
//Sum of k smallest elements in BST
public class BST
{

static class Node
{
int data;
Node left,right;
}
public Node root;
public int counter,result;
//Class constructors
BST()
{
root=null;
counter=0;
result=0;
}

//insert  element
{
//Create a dynamic node of binary search tree
Node new_node = new Node();

if(new_node != null)
{
//Set data and pointer values
new_node.data = data;
//Initially node left-pointer is null
new_node.left = null;
//Initially node right-pointer is null
new_node.right = null;

if(root == null)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
Node find = root;

//add new node to proper position
while(find != null)
{
if(find.data >= data)
{
if(find.left==null)
{
find.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if(find.right == null)
{
find.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
System.out.println("Memory Overflow");
}
}
public void   k_smallest( Node root,int k)
{
if(root != null &&  counter < k)
{

k_smallest(root.left,k);
if( counter<k)
{
result = result + root.data;
counter++;
}
k_smallest(root.right,k);
}
}
public void  smallest_sum(int k)
{
if(k<=0)
{
return;
}
if(root != null)
{
result=0;
counter=0;
k_smallest(root,k);
System.out.println("  "+result);
}

}

public static void main(String[] args)
{

BST obj = new BST();

/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2   7        12
*/

obj.smallest_sum(3);
obj.smallest_sum(5);

}
}``````

#### Output

``````  0
7
``````
``````#Python Program
#Sum of k smallest elements in BST
class Node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None

class BST:

def __init__(self):

#Assign default value
self.root=None
self.counter=0
self.result=0

#insert  element

#Create a dynamic node of binary search tree
new_node = Node(data)

if(self.root == None):
#When adds a first node in binary tree
self.root = new_node

else:
find = self.root

#add new node to proper position
while(find != None):

if(find.data >= data):

if(find.left==None):

find.left = new_node
break

else:

#visit left sub-tree
find = find.left

else:

if(find.right == None):

find.right = new_node
break

else:

#visit right sub-tree
find = find.right

def   k_smallest(self, root, k) :

if(root != None  and  self.counter < k) :

self.k_smallest(root.left,k)
if(self.counter < k) :

self.result= self.result + root.data
self.counter += 1
self.k_smallest(root.right,k)
def   smallest_sum(self, k) :

if(k<=0)  :

return
if(self.root != None) :

self.result=0
self.counter=0
self.k_smallest(self.root,k)
print("  ",self.result)

def main():

#Make a object of BST class
obj=  BST()
#Add nodes in binary search tree
#
#             5
#           /    \
#          3      9
#         / \     / \
#        1   4   8   11
#       / \     /      \
#      -3  2   7        12
#
obj.smallest_sum(3)
obj.smallest_sum(5)

if __name__ =="__main__":
main()``````

#### Output

``````   0
7``````
``````//C# program
//Sum of k smallest elements in BST

using System;
public class Node
{
public int data;
public Node left,right;
}
public class BST
{

public Node root;
public int counter,result;
//Class constructors
BST()
{
root=null;
counter=0;
result=0;
}

//insert  element
{
//Create a dynamic node of binary search tree
Node new_node = new Node();

if(new_node != null)
{
//Set data and pointer values
new_node.data = data;
//Initially node left-pointer is null
new_node.left = null;
//Initially node right-pointer is null
new_node.right = null;

if(root == null)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
Node find = root;

//add new node to proper position
while(find != null)
{
if(find.data >= data)
{
if(find.left==null)
{
find.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if(find.right == null)
{
find.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
Console.WriteLine("Memory Overflow");
}
}
public void   k_smallest( Node root,int k)
{
if(root != null &&  counter < k)
{

k_smallest(root.left,k);
if( counter<k)
{
result = result + root.data;
counter++;
}
k_smallest(root.right,k);
}
}
public void  smallest_sum(int k)
{
if(k<=0)
{
return;
}
if(root != null)
{
result=0;
counter=0;
k_smallest(root,k);
Console.WriteLine("  "+result);
}

}

public static void Main(String[] args)
{

BST obj = new BST();

/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2   7        12
*/

obj.smallest_sum(3);
obj.smallest_sum(5);

}
}``````

#### Output

``````  0
7``````
``````<?php
//Php program
//Sum of k smallest elements in BST
class Node
{
public \$data;
public \$left;
public \$right;
function __construct(\$data)
{
\$this->data = \$data;
\$this->length = NULL;
\$this->right = NULL;
}
}
class BST
{

public \$root;
function __construct()
{
\$root=NULL;
}
//Adding a new node in binary search tree
{
//Create a dynamic node of binary search tree
\$new_node = new Node(\$data);

if(\$this->root == NULL)
{
//When adds a first node in binary tree
\$this->root = \$new_node;
}
else
{
\$find = \$this->root;

//add new node to proper position
while(\$find != NULL)
{
if(\$find->data >= \$data)
{
if(\$find->left==NULL)
{
\$find->left = \$new_node;
break;
}
else
{
//visit left sub-tree
\$find = \$find->left;
}
}
else
{
if(\$find->right == NULL)
{
\$find->right = \$new_node;
break;
}
else
{
//visit right sub-tree
\$find = \$find->right;
}
}
}
}

}

function  k_smallest( \$root, &\$result, &\$counter, \$k)
{
if(\$root != NULL && \$counter < \$k)
{

\$this->k_smallest(\$root->left,\$result,\$counter,\$k);
if(\$counter < \$k)
{
\$result=\$result + \$root->data;
\$counter++;
}
\$this->k_smallest(\$root->right,\$result,\$counter,\$k);
}
}
function  smallest_sum( \$k)
{
if(\$k<=0)
{
return;
}
if(\$this->root != NULL)
{
\$result=0;
\$counter=0;
\$this->k_smallest(\$this->root,\$result,\$counter,\$k);
echo "  ".\$result."\n";
}

}

}
function main()
{
//Make a object of BST class
\$obj= new BST();

//Add nodes in binary search tree
/*
5
/    \
3      9
/ \     / \
1   4   8   11
/ \     /      \
-3  2   7        12
*/

\$obj->smallest_sum(3);
\$obj->smallest_sum(5);

}
main();
?>``````

#### Output

``````  0
7
``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.