Suma de k elementos más pequeños en BST

Árbol de búsqueda binario dado . La tarea es encontrar la suma de todos los elementos menores que e iguales al K-ésimo elemento más pequeño.

Ejemplos: 

C++

// c++ program to find Sum Of All Elements smaller
// than or equal to Kth Smallest Element In BST
#include <bits/stdc++.h>
using namespace std;
 
/* Binary tree Node */
struct Node
{
    int data;
    Node* left, * right;
};
 
// utility function new Node of BST
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;
}
 
// A utility function to insert a new Node
//  with given key in BST and also maintain lcount ,Sum
struct Node * insert(Node *root, int key)
{
    // If the tree is empty, return a new Node
    if (root == NULL)
        return createNode(key);
 
    // Otherwise, recur down the tree
    if (root->data > key)
        root->left = insert(root->left, key);
 
    else if (root->data < key)
        root->right = insert(root->right, key);
 
    // return the (unchanged) Node pointer
    return root;
}
 
// function return sum of all element smaller than
// and equal to Kth smallest element
int ksmallestElementSumRec(Node *root, int k, int &count)
{
    // Base cases
    if (root == NULL)
        return 0;
    if (count > k)
        return 0;
 
    // Compute sum of elements in left subtree
    int res = ksmallestElementSumRec(root->left, k, count);
    if (count >= k)
        return res;
 
    // Add root's data
    res += root->data;
 
    // Add current Node
    count++;
    if (count >= k)
      return res;
 
    // If count is less than k, return right subtree Nodes
    return res + ksmallestElementSumRec(root->right, k, count);
}
 
// Wrapper over ksmallestElementSumRec()
int ksmallestElementSum(struct Node *root, int k)
{
   int count = 0;
   ksmallestElementSumRec(root, k, count);
}
 
/* Driver program to test above functions */
int main()
{
 
    /*    20
        /    \
       8     22
     /   \
    4     12
         /   \
        10    14
          */
    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;
}

Java

// Java program to find Sum Of All Elements smaller
// than or equal to Kth Smallest Element In BST
import java.util.*;
class GFG
{
 
  /* Binary tree Node */
  static class Node
  {
    int data;
    Node left,  right;
  };
 
  // utility function new Node of BST
  static Node createNode(int data)
  {
    Node  new_Node = new Node();
    new_Node.left = null;
    new_Node.right = null;
    new_Node.data = data;
    return new_Node;
  }
 
  // A utility function to insert a new Node
  //  with given key in BST and also maintain lcount ,Sum
  static Node  insert(Node root, int key)
  {
 
    // If the tree is empty, return a new Node
    if (root == null)
      return createNode(key);
 
    // Otherwise, recur down the tree
    if (root.data > key)
      root.left = insert(root.left, key);
    else if (root.data < key)
      root.right = insert(root.right, key);
 
    // return the (unchanged) Node pointer
    return root;
  }
 
 
  static int count = 0;
 
  // function return sum of all element smaller than
  // and equal to Kth smallest element
  static int ksmallestElementSumRec(Node root, int k)
  {
 
    // Base cases
    if (root == null)
      return 0;
    if (count > k)
      return 0;
 
    // Compute sum of elements in left subtree
    int res = ksmallestElementSumRec(root.left, k);
    if (count >= k)
      return res;
 
    // Add root's data
    res += root.data;
 
    // Add current Node
    count++;
    if (count >= k)
      return res;
 
    // If count is less than k, return right subtree Nodes
    return res + ksmallestElementSumRec(root.right, k);
  }
 
  // Wrapper over ksmallestElementSumRec()
  static int ksmallestElementSum(Node root, int k)
  {
 
    int res = ksmallestElementSumRec(root, k);
    return res;
  }
 
  /* Driver program to test above functions */
  public static void main(String[] args)
  {
 
    /*    20
        /    \
       8     22
     /   \
    4     12
         /   \
        10    14
          */
    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;
    int count = ksmallestElementSum(root, k);
    System.out.println(count);
  }
}
 
// This code is contributed by aashish1995

Python3

# Python3 program to find Sum Of All
# Elements smaller than or equal to
# Kth Smallest Element In BST
 
INT_MAX = 2147483647
 
# Binary Tree Node
""" utility that allocates a newNode
with the given key """
class createNode:
 
    # Construct to create a newNode
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
 
# A utility function to insert a new
# Node with given key in BST and also
# maintain lcount ,Sum
def insert(root, key) :
 
    # If the tree is empty, return a new Node
    if (root == None) :
        return createNode(key)
 
    # Otherwise, recur down the tree
    if (root.data > key) :
        root.left = insert(root.left, key)
 
    else if (root.data < key):
        root.right = insert(root.right, key)
 
    # return the (unchanged) Node pointer
    return root
 
# function return sum of all element smaller
# than and equal to Kth smallest element
def ksmallestElementSumRec(root, k, count) :
 
    # Base cases
    if (root == None) :
        return 0
    if (count[0] > k[0]) :
        return 0
 
    # Compute sum of elements in left subtree
    res = ksmallestElementSumRec(root.left, k, count)
    if (count[0] >= k[0]) :
        return res
 
    # Add root's data
    res += root.data
 
    # Add current Node
    count[0] += 1
    if (count[0] >= k[0]) :
        return res
 
    # If count is less than k, return
    # right subtree Nodes
    return res + ksmallestElementSumRec(root.right,
                                        k, count)
 
# Wrapper over ksmallestElementSumRec()
def ksmallestElementSum(root, k):
    count = [0]
    return ksmallestElementSumRec(root, k, count)
 
# Driver Code
if __name__ == '__main__':
 
    """ 20
        / \
    8 22
    / \
    4 12
        / \
        10 14
        """
    root = None
    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)
     
    k = [3]
    print(ksmallestElementSum(root, k))
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

C#

// C# program to find Sum Of All Elements smaller
// than or equal to Kth Smallest Element In BST
using System;
 
public class GFG
{
 
  /* Binary tree Node */
  public class Node
  {
    public int data;
    public Node left,  right;
  };
 
  // utility function new Node of BST
  static Node createNode(int data)
  {
    Node  new_Node = new Node();
    new_Node.left = null;
    new_Node.right = null;
    new_Node.data = data;
    return new_Node;
  }
 
  // A utility function to insert a new Node
  //  with given key in BST and also maintain lcount ,Sum
  static Node  insert(Node root, int key)
  {
 
    // If the tree is empty, return a new Node
    if (root == null)
      return createNode(key);
 
    // Otherwise, recur down the tree
    if (root.data > key)
      root.left = insert(root.left, key);
    else if (root.data < key)
      root.right = insert(root.right, key);
 
    // return the (unchanged) Node pointer
    return root;
  }
  static int count = 0;
 
  // function return sum of all element smaller than
  // and equal to Kth smallest element
  static int ksmallestElementSumRec(Node root, int k)
  {
 
    // Base cases
    if (root == null)
      return 0;
    if (count > k)
      return 0;
 
    // Compute sum of elements in left subtree
    int res = ksmallestElementSumRec(root.left, k);
    if (count >= k)
      return res;
 
    // Add root's data
    res += root.data;
 
    // Add current Node
    count++;
    if (count >= k)
      return res;
 
    // If count is less than k, return right subtree Nodes
    return res + ksmallestElementSumRec(root.right, k);
  }
 
  // Wrapper over ksmallestElementSumRec()
  static int ksmallestElementSum(Node root, int k)
  {
 
    int res = ksmallestElementSumRec(root, k);
    return res;
  }
 
  /* Driver program to test above functions */
  public static void Main(String[] args)
  {
 
    /*    20
        /    \
       8     22
     /   \
    4     12
         /   \
        10    14
          */
    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;
    int count = ksmallestElementSum(root, k);
    Console.WriteLine(count);
  }
}
 
// This code is contributed by aashish1995

Javascript

<script>
 
// JavaScript program to find
// Sum Of All Elements smaller
// than or equal to Kth Smallest Element In BST
 /* Binary tree Node */
class Node {
    constructor() {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
}
 
  // utility function new Node of BST
  function createNode(data)
  {
    var  new_Node = new Node();
    new_Node.left = null;
    new_Node.right = null;
    new_Node.data = data;
    return new_Node;
  }
 
  // A utility function to insert a new Node
  //  with given key in BST and also maintain lcount ,Sum
  function  insert(root , key)
  {
 
    // If the tree is empty, return a new Node
    if (root == null)
      return createNode(key);
 
    // Otherwise, recur down the tree
    if (root.data > key)
      root.left = insert(root.left, key);
    else if (root.data < key)
      root.right = insert(root.right, key);
 
    // return the (unchanged) Node pointer
    return root;
  }
  var count = 0;
 
  // function return sum of all element smaller than
  // and equal to Kth smallest element
  function ksmallestElementSumRec(root , k)
  {
 
    // Base cases
    if (root == null)
      return 0;
    if (count > k)
      return 0;
 
    // Compute sum of elements in left subtree
    var res = ksmallestElementSumRec(root.left, k);
    if (count >= k)
      return res;
 
    // Add root's data
    res += root.data;
 
    // Add current Node
    count++;
    if (count >= k)
      return res;
 
    // If count is less than k, return right subtree Nodes
    return res + ksmallestElementSumRec(root.right, k);
  }
 
  // Wrapper over ksmallestElementSumRec()
  function ksmallestElementSum(root , k)
  {
 
    var res = ksmallestElementSumRec(root, k);
    return res;
  }
 
  /* Driver program to test above functions */
   
  
 
    /*    20
        /    \
       8     22
     /   \
    4     12
         /   \
        10    14
          */
    var 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);
 
    var k = 3;
    var count = ksmallestElementSum(root, k);
    document.write(count);
 
// This code is contributed by todaysgaurav
 
</script>

C++

// C++ program to find Sum Of All Elements smaller
// than or equal t Kth Smallest Element In BST
#include <bits/stdc++.h>
using namespace std;
 
/* Binary tree Node */
struct Node
{
    int data;
    int lCount;
    int Sum ;
    Node* left;
    Node* right;
};
 
//utility function new Node of BST
struct Node *createNode(int data)
{
    Node * new_Node = new Node;
    new_Node->left = NULL;
    new_Node->right = NULL;
    new_Node->data = data;
    new_Node->lCount = 0 ;
    new_Node->Sum = 0;
    return new_Node;
}
 
// A utility function to insert a new Node with
// given key in BST and also maintain lcount ,Sum
struct Node * insert(Node *root, int key)
{
    // If the tree is empty, return a new Node
    if (root == NULL)
        return createNode(key);
 
    // Otherwise, recur down the tree
    if (root->data > key)
    {
        // increment lCount of current Node
        root->lCount++;
 
        // increment current Node sum by adding
        // key into it
        root->Sum += key;
 
        root->left= insert(root->left , key);
    }
    else if (root->data < key )
        root->right= insert (root->right , key );
 
    // return the (unchanged) Node pointer
    return root;
}
 
// function return sum of all element smaller than and equal
// to Kth smallest element
void ksmallestElementSumRec(Node *root, int k , int &temp_sum)
{
    if (root == NULL)
        return ;
 
    // if we fount k smallest element then break the function
    if ((root->lCount + 1) == k)
    {
        temp_sum += root->data + root->Sum ;
        return ;
    }
 
    else if (k > root->lCount)
    {
        // store sum of all element smaller than current root ;
        temp_sum += root->data + root->Sum;
 
        // decremented k and call right sub-tree
        k = k -( root->lCount + 1);
        ksmallestElementSumRec(root->right , k , temp_sum);
    }
    else // call left sub-tree
        ksmallestElementSumRec(root->left , k , temp_sum );
}
 
// Wrapper over ksmallestElementSumRec()
int ksmallestElementSum(struct Node *root, int k)
{
    int sum = 0;
    ksmallestElementSumRec(root, k, sum);
    return sum;
}
 
/* Driver program to test above functions */
int main()
{
    /*    20
        /    \
       8     22
     /   \
    4     12
         /   \
        10    14
          */
    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;
}

Java

// Java program to find Sum Of All Elements smaller
// than or equal t Kth Smallest Element In BST
 
import java.util.*;
 
class GFG{
 
/* Binary tree Node */
static class Node
{
    int data;
    int lCount;
    int Sum ;
    Node left;
    Node right;
};
 
//utility function new Node of BST
static Node createNode(int data)
{
    Node  new_Node = new Node();
    new_Node.left = null;
    new_Node.right = null;
    new_Node.data = data;
    new_Node.lCount = 0 ;
    new_Node.Sum = 0;
    return new_Node;
}
 
// A utility function to insert a new Node with
// given key in BST and also maintain lcount ,Sum
static Node  insert(Node root, int key)
{
    // If the tree is empty, return a new Node
    if (root == null)
        return createNode(key);
 
    // Otherwise, recur down the tree
    if (root.data > key)
    {
        // increment lCount of current Node
        root.lCount++;
 
        // increment current Node sum by adding
        // key into it
        root.Sum += key;
 
        root.left= insert(root.left , key);
    }
    else if (root.data < key )
        root.right= insert (root.right , key );
 
    // return the (unchanged) Node pointer
    return root;
}
 
static int temp_sum;
// function return sum of all element smaller than and equal
// to Kth smallest element
static void ksmallestElementSumRec(Node root, int k )
{
    if (root == null)
        return ;
 
    // if we fount k smallest element then break the function
    if ((root.lCount + 1) == k)
    {
        temp_sum += root.data + root.Sum ;
        return ;
    }
 
    else if (k > root.lCount)
    {
        // store sum of all element smaller than current root ;
        temp_sum += root.data + root.Sum;
 
        // decremented k and call right sub-tree
        k = k -( root.lCount + 1);
        ksmallestElementSumRec(root.right , k );
    }
    else // call left sub-tree
        ksmallestElementSumRec(root.left , k );
}
 
// Wrapper over ksmallestElementSumRec()
static void ksmallestElementSum(Node root, int k)
{
    temp_sum = 0;
    ksmallestElementSumRec(root, k);
}
 
/* Driver program to test above functions */
public static void main(String[] args)
{
    /*    20
        /    \
       8     22
     /   \
    4     12
         /   \
        10    14
          */
    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;
     ksmallestElementSum(root, k);
     System.out.println(temp_sum);
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program to find Sum Of All Elements
# smaller than or equal t Kth Smallest Element In BST
 
# utility function new Node of BST
class createNode:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.lCount = 0
        self.Sum = 0
        self.left = None
        self.right = None
 
# A utility function to insert a new Node with
# given key in BST and also maintain lcount ,Sum
def insert(root, key):
     
    # If the tree is empty, return a new Node
    if root == None:
        return createNode(key)
 
    # Otherwise, recur down the tree
    if root.data > key:
         
        # increment lCount of current Node
        root.lCount += 1
 
        # increment current Node sum by
        # adding key into it
        root.Sum += key
 
        root.left= insert(root.left , key)
    else if root.data < key:
        root.right= insert (root.right , key)
 
    # return the (unchanged) Node pointer
    return root
 
# function return sum of all element smaller
# than and equal to Kth smallest element
def ksmallestElementSumRec(root, k , temp_sum):
    if root == None:
        return
 
    # if we fount k smallest element
    # then break the function
    if (root.lCount + 1) == k:
        temp_sum[0] += root.data + root.Sum
        return
 
    else if k > root.lCount:
         
        # store sum of all element smaller
        # than current root ;
        temp_sum[0] += root.data + root.Sum
 
        # decremented k and call right sub-tree
        k = k -( root.lCount + 1)
        ksmallestElementSumRec(root.right,
                               k, temp_sum)
    else: # call left sub-tree
        ksmallestElementSumRec(root.left,
                               k, temp_sum)
 
# Wrapper over ksmallestElementSumRec()
def ksmallestElementSum(root, k):
    Sum = [0]
    ksmallestElementSumRec(root, k, Sum)
    return Sum[0]
 
# Driver Code
if __name__ == '__main__':
     
    # 20
    # / \
    # 8     22
    # / \
    #4     12
    #     / \
    # 10 14
    #    
    root = None
    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)
 
    k = 3
    print(ksmallestElementSum(root, k))
 
# This code is contributed by PranchalK

C#

// C# program to find Sum Of All Elements smaller
// than or equal t Kth Smallest Element In BST
using System;
public class GFG
{
 
/* Binary tree Node */
public class Node
{
   public int data;
   public int lCount;
   public int Sum ;
   public Node left;
   public Node right;
};
 
// utility function new Node of BST
static Node createNode(int data)
{
    Node  new_Node = new Node();
    new_Node.left = null;
    new_Node.right = null;
    new_Node.data = data;
    new_Node.lCount = 0 ;
    new_Node.Sum = 0;
    return new_Node;
}
 
// A utility function to insert a new Node with
// given key in BST and also maintain lcount ,Sum
static Node  insert(Node root, int key)
{
   
    // If the tree is empty, return a new Node
    if (root == null)
        return createNode(key);
 
    // Otherwise, recur down the tree
    if (root.data > key)
    {
       
        // increment lCount of current Node
        root.lCount++;
 
        // increment current Node sum by adding
        // key into it
        root.Sum += key;
        root.left = insert(root.left , key);
    }
    else if (root.data < key )
        root.right = insert (root.right , key );
 
    // return the (unchanged) Node pointer
    return root;
}
 
static int temp_sum;
   
// function return sum of all element smaller than and equal
// to Kth smallest element
static void ksmallestElementSumRec(Node root, int k )
{
    if (root == null)
        return ;
 
    // if we fount k smallest element then break the function
    if ((root.lCount + 1) == k)
    {
        temp_sum += root.data + root.Sum ;
        return ;
    }
 
    else if (k > root.lCount)
    {
       
        // store sum of all element smaller than current root ;
        temp_sum += root.data + root.Sum;
 
        // decremented k and call right sub-tree
        k = k -( root.lCount + 1);
        ksmallestElementSumRec(root.right , k );
    }
    else // call left sub-tree
        ksmallestElementSumRec(root.left , k );
}
 
// Wrapper over ksmallestElementSumRec()
static void ksmallestElementSum(Node root, int k)
{
    temp_sum = 0;
    ksmallestElementSumRec(root, k);
}
 
/* Driver program to test above functions */
public static void Main(String[] args)
{
    /*    20
        /    \
       8     22
     /   \
    4     12
         /   \
        10    14
          */
    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;
     ksmallestElementSum(root, k);
     Console.WriteLine(temp_sum);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
      // JavaScript program to find Sum Of All Elements smaller
      // than or equal t Kth Smallest Element In BST
      /* Binary tree Node */
      class Node {
        constructor() {
          this.data = 0;
          this.lCount = 0;
          this.Sum = 0;
          this.left = null;
          this.right = null;
        }
      }
 
      // utility function new Node of BST
      function createNode(data) {
        var new_Node = new Node();
        new_Node.left = null;
        new_Node.right = null;
        new_Node.data = data;
        new_Node.lCount = 0;
        new_Node.Sum = 0;
        return new_Node;
      }
 
      // A utility function to insert a new Node with
      // given key in BST and also maintain lcount ,Sum
      function insert(root, key) {
        // If the tree is empty, return a new Node
        if (root == null) return createNode(key);
 
        // Otherwise, recur down the tree
        if (root.data > key) {
          // increment lCount of current Node
          root.lCount++;
 
          // increment current Node sum by adding
          // key into it
          root.Sum += key;
          root.left = insert(root.left, key);
        } else if (root.data < key)
        root.right = insert(root.right, key);
 
        // return the (unchanged) Node pointer
        return root;
      }
 
      var temp_sum = 0;
 
      // function return sum of all element smaller than and equal
      // to Kth smallest element
      function ksmallestElementSumRec(root, k) {
        if (root == null) return;
 
        // if we fount k smallest element then break the function
        if (root.lCount + 1 == k) {
          temp_sum += root.data + root.Sum;
          return;
        } else if (k > root.lCount) {
          // store sum of all element smaller than current root ;
          temp_sum += root.data + root.Sum;
 
          // decremented k and call right sub-tree
          k = k - (root.lCount + 1);
          ksmallestElementSumRec(root.right, k);
        } // call left sub-tree
        else ksmallestElementSumRec(root.left, k);
      }
 
      // Wrapper over ksmallestElementSumRec()
      function ksmallestElementSum(root, k) {
        temp_sum = 0;
        ksmallestElementSumRec(root, k);
      }
 
      /* Driver program to test above functions */
      /*  20
        /    \
       8     22
     /   \
    4     12
         /   \
        10    14
          */
      var 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);
 
      var k = 3;
      ksmallestElementSum(root, k);
      document.write(temp_sum);
       
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *