Dado un árbol de búsqueda binaria (BST) y un número entero positivo k, encuentre el k-ésimo elemento más grande en el árbol de búsqueda binaria.
Por ejemplo, en el siguiente BST, si k = 3, la salida debería ser 14, y si k = 5, la salida debería ser 10.
C++
// C++ program to find k'th largest element in BST
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int key;
Node *left, *right;
};
// A utility function to create a new BST node
Node *newNode(int item)
{
Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A function to find k'th largest element in a given tree.
void kthLargestUtil(Node *root, int k, int &c)
{
// Base cases, the second condition is important to
// avoid unnecessary recursive calls
if (root == NULL || c >= k)
return;
// Follow reverse inorder traversal so that the
// largest element is visited first
kthLargestUtil(root->right, k, c);
// Increment count of visited nodes
c++;
// If c becomes k now, then this is the k'th largest
if (c == k)
{
cout << "K'th largest element is "
<< root->key << endl;
return;
}
// Recur for left subtree
kthLargestUtil(root->left, k, c);
}
// Function to find k'th largest element
void kthLargest(Node *root, int k)
{
// Initialize count of nodes visited as 0
int c = 0;
// Note that c is passed by reference
kthLargestUtil(root, k, c);
}
/* A utility function to insert a new node with given key in BST */
Node* insert(Node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
int c = 0;
for (int k=1; k<=7; k++)
kthLargest(root, k);
return 0;
}
Java
// Java code to find k'th largest element in BST
// A binary tree node
class Node {
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
class BinarySearchTree {
// Root of BST
Node root;
// Constructor
BinarySearchTree()
{
root = null;
}
// function to insert nodes
public void insert(int data)
{
this.root = this.insertRec(this.root, data);
}
/* A utility function to insert a new node
with given key in BST */
Node insertRec(Node node, int data)
{
/* If the tree is empty, return a new node */
if (node == null) {
this.root = new Node(data);
return this.root;
}
if (data == node.data) {
return node;
}
/* Otherwise, recur down the tree */
if (data < node.data) {
node.left = this.insertRec(node.left, data);
} else {
node.right = this.insertRec(node.right, data);
}
return node;
}
// class that stores the value of count
public class count {
int c = 0;
}
// utility function to find kth largest no in
// a given tree
void kthLargestUtil(Node node, int k, count C)
{
// Base cases, the second condition is important to
// avoid unnecessary recursive calls
if (node == null || C.c >= k)
return;
// Follow reverse inorder traversal so that the
// largest element is visited first
this.kthLargestUtil(node.right, k, C);
// Increment count of visited nodes
C.c++;
// If c becomes k now, then this is the k'th largest
if (C.c == k) {
System.out.println(k + "th largest element is " +
node.data);
return;
}
// Recur for left subtree
this.kthLargestUtil(node.left, k, C);
}
// Method to find the kth largest no in given BST
void kthLargest(int k)
{
count c = new count(); // object of class count
this.kthLargestUtil(this.root, k, c);
}
// Driver function
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
for (int i = 1; i <= 7; i++) {
tree.kthLargest(i);
}
}
}
// This code is contributed by Kamal Rawal
Python3
# Python3 program to find k'th largest
# element in BST
class Node:
# Constructor to create a new node
def __init__(self, data):
self.key = data
self.left = None
self.right = None
# A function to find k'th largest
# element in a given tree.
def kthLargestUtil(root, k, c):
# Base cases, the second condition
# is important to avoid unnecessary
# recursive calls
if root == None or c[0] >= k:
return
# Follow reverse inorder traversal
# so that the largest element is
# visited first
kthLargestUtil(root.right, k, c)
# Increment count of visited nodes
c[0] += 1
# If c becomes k now, then this is
# the k'th largest
if c[0] == k:
print("K'th largest element is",
root.key)
return
# Recur for left subtree
kthLargestUtil(root.left, k, c)
# Function to find k'th largest element
def kthLargest(root, k):
# Initialize count of nodes
# visited as 0
c = [0]
# Note that c is passed by reference
kthLargestUtil(root, k, c)
# A utility function to insert a new
# node with given key in BST */
def insert(node, key):
# If the tree is empty,
# return a new node
if node == None:
return Node(key)
# Otherwise, recur down the tree
if key < node.key:
node.left = insert(node.left, key)
elif key > node.key:
node.right = insert(node.right, key)
# return the (unchanged) node pointer
return node
# Driver Code
if __name__ == '__main__':
# Let us create following BST
# 50
# / \
# 30 70
# / \ / \
# 20 40 60 80 */
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 20)
insert(root, 40)
insert(root, 70)
insert(root, 60)
insert(root, 80)
for k in range(1,8):
kthLargest(root, k)
# This code is contributed by PranchalK
C#
using System;
// C# code to find k'th largest element in BST
// A binary tree node
public class Node
{
public int data;
public Node left, right;
public Node(int d)
{
data = d;
left = right = null;
}
}
public class BinarySearchTree
{
// Root of BST
public Node root;
// Constructor
public BinarySearchTree()
{
root = null;
}
// function to insert nodes
public virtual void insert(int data)
{
this.root = this.insertRec(this.root, data);
}
/* A utility function to insert a new node
with given key in BST */
public virtual Node insertRec(Node node, int data)
{
/* If the tree is empty, return a new node */
if (node == null)
{
this.root = new Node(data);
return this.root;
}
if (data == node.data)
{
return node;
}
/* Otherwise, recur down the tree */
if (data < node.data)
{
node.left = this.insertRec(node.left, data);
}
else
{
node.right = this.insertRec(node.right, data);
}
return node;
}
// class that stores the value of count
public class count
{
private readonly BinarySearchTree outerInstance;
public count(BinarySearchTree outerInstance)
{
this.outerInstance = outerInstance;
}
internal int c = 0;
}
// utility function to find kth largest no in
// a given tree
public virtual void kthLargestUtil(Node node, int k, count C)
{
// Base cases, the second condition is important to
// avoid unnecessary recursive calls
if (node == null || C.c >= k)
{
return;
}
// Follow reverse inorder traversal so that the
// largest element is visited first
this.kthLargestUtil(node.right, k, C);
// Increment count of visited nodes
C.c++;
// If c becomes k now, then this is the k'th largest
if (C.c == k)
{
Console.WriteLine(k + "th largest element is " + node.data);
return;
}
// Recur for left subtree
this.kthLargestUtil(node.left, k, C);
}
// Method to find the kth largest no in given BST
public virtual void kthLargest(int k)
{
count c = new count(this); // object of class count
this.kthLargestUtil(this.root, k, c);
}
// Driver function
public static void Main(string[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
for (int i = 1; i <= 7; i++)
{
tree.kthLargest(i);
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// javascript code to find k'th largest element in BST
// A binary tree node
class Node {
constructor(d)
{
this.data = d;
this.left = this.right = null;
}
}
// Root of BST
var root = null;
// Constructor
// function to insert nodes
function insert(data)
{
this.root = this.insertRec(this.root, data);
}
/* A utility function to insert a new node
with given key in BST */
function insertRec( node , data)
{
/* If the tree is empty, return a new node */
if (node == null) {
this.root = new Node(data);
return this.root;
}
if (data == node.data) {
return node;
}
/* Otherwise, recur down the tree */
if (data < node.data) {
node.left = this.insertRec(node.left, data);
} else {
node.right = this.insertRec(node.right, data);
}
return node;
}
// class that stores the value of count
class count {
constructor(){this.c = 0;}
}
// utility function to find kth largest no in
// a given tree
function kthLargestUtil( node , k, C)
{
// Base cases, the second condition is important to
// avoid unnecessary recursive calls
if (node == null || C.c >= k)
return;
// Follow reverse inorder traversal so that the
// largest element is visited first
this.kthLargestUtil(node.right, k, C);
// Increment count of visited nodes
C.c++;
// If c becomes k now, then this is the k'th largest
if (C.c == k) {
document.write(k + "th largest element is " +
node.data+"<br/>");
return;
}
// Recur for left subtree
this.kthLargestUtil(node.left, k, C);
}
// Method to find the kth largest no in given BST
function kthLargest(k)
{
c = new count(); // object of class count
this.kthLargestUtil(this.root, k, c);
}
// Driver function
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
insert(50);
insert(30);
insert(20);
insert(40);
insert(70);
insert(60);
insert(80);
for (i = 1; i <= 7; i++) {
kthLargest(i);
}
// This code contributed by gauravrajput1
</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