Sum of k smallest elements in BST

Sum of initial k smallest element 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
  
  */                

  add(&root,5); 
  add(&root,3); 
  add(&root,9); 
  add(&root,1); 
  add(&root,4); 
  add(&root,8); 
  add(&root,11); 
  add(&root,-3); 
  add(&root,2); 
  add(&root,7); 
  add(&root,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 add(int);
  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
void BST :: add(int data)
{
  //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.add(5); 
  obj.add(3); 
  obj.add(9); 
  obj.add(1); 
  obj.add(4); 
  obj.add(8); 
  obj.add(11); 
  obj.add(-3); 
  obj.add(2); 
  obj.add(7); 
  obj.add(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
  public void add(int data)
  {
    //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.add(5); 
    obj.add(3); 
    obj.add(9); 
    obj.add(1); 
    obj.add(4); 
    obj.add(8); 
    obj.add(11); 
    obj.add(-3); 
    obj.add(2); 
    obj.add(7); 
    obj.add(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
  def add(self,data):

    #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.add(5) 
  obj.add(3) 
  obj.add(9) 
  obj.add(1) 
  obj.add(4) 
  obj.add(8) 
  obj.add(11) 
  obj.add(-3) 
  obj.add(2) 
  obj.add(7) 
  obj.add(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
  public void add(int data)
  {
    //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.add(5); 
    obj.add(3); 
    obj.add(9); 
    obj.add(1); 
    obj.add(4); 
    obj.add(8); 
    obj.add(11); 
    obj.add(-3); 
    obj.add(2); 
    obj.add(7); 
    obj.add(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
  public function add($data)
  {
    //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->add(5); 
  $obj->add(3); 
  $obj->add(9); 
  $obj->add(1); 
  $obj->add(4); 
  $obj->add(8); 
  $obj->add(11); 
  $obj->add(-3); 
  $obj->add(2); 
  $obj->add(7); 
  $obj->add(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.

New Comment







© 2021, kalkicode.com, All rights reserved