Á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