Dado un BST perfecto con N Nodes y un número entero K, la tarea es encontrar el K -ésimo elemento más pequeño presente en el árbol.
Ejemplo:
Input:
K = 3, N = 15
50
/ \
30 70
/ \ / \
20 40 60 80
/\ /\ /\ / \
14 25 35 45 55 65 75 85
Output: 25
Explanation:
The 3rd smallest element
in the given BST is 25
Input:
K = 9, N = 15
50
/ \
30 70
/ \ / \
20 40 60 80
/\ /\ /\ / \
14 25 35 45 55 65 75 85
Output: 55
Explanation:
The 9th smallest element
in the given BST is 55
Enfoque ingenuo: realice el recorrido en orden en un BST perfecto, como el recorrido de morris o la solución recursiva, que visita cada Node y devuelve la clave de visita k-ésima. Se necesita una complejidad de tiempo O(N) para completar la tarea.
Enfoque eficiente:
dado que el BST dado es perfecto y ya se conoce el número de Nodes de todo el árbol, la complejidad computacional para resolver el problema se puede reducir a log(N) . Siga los pasos que se indican a continuación para resolver el problema:
- en un árbol BST perfecto(N), |N| siempre será impar en un árbol binario perfecto, la ubicación de la mediana en cualquier BST perfecto es piso(|N|/2) + 1.
- Calcule el número de Nodes en cada subárbol dividiendo el total de Nodes como piso (| N| / 2).
- El subárbol izquierdo del BST perfecto siempre contendrá el K-ésimo elemento más pequeño si :
- K < ubicación (mediana (N)) = M esto se debe a que el M elemento más pequeño siempre será más grande que el K elemento más pequeño y cada elemento en el subárbol derecho será más grande que el M elemento más pequeño
- El sub-árbol derecho de Perfect BST siempre contendrá un R -ésimo elemento más pequeño si :
- K > ubicación (mediana (N)) = M, en este caso, K – ubicación (mediana (N)) = R es el elemento más pequeño de R en el subárbol derecho. Esto se debe a que el R elemento más pequeño del subárbol derecho es mayor que el M elemento más pequeño y cada elemento del subárbol izquierdo es más pequeño que el M elemento más pequeño, pero el R elemento más pequeño es mayor que todos ellos. Uno puede pensar en R como el nuevo número cuando se pueden ignorar al menos M posibilidades más pequeñas. El elemento más pequeño de R es el elemento más pequeño de K cuando se repite en el subárbol derecho (pero tenga en cuenta que R !=¡K!).
- Si K es ubicación (mediana (T)), entonces ese Node contiene el K-ésimo elemento más pequeño en BST perfecto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find K-th
// smallest element in a
// perfect BST
#include <bits/stdc++.h>
using namespace std;
// A BST node
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 utility function to insert a
// new node with given key in BST
Node* insert(Node* node, int key)
{
// If the tree is empty
if (node == NULL)
return newNode(key);
// Recur down the left
// subtree for smaller values
if (key < node->key)
node->left = insert(node->left, key);
// Recur down the right
// subtree for smaller values
else if (key > node->key)
node->right = insert(node->right, key);
// Return the (unchanged) node pointer
return node;
}
// FUnction to find Kth Smallest
// element in a perfect BST
bool KSmallestPerfectBST(Node* root, int k,
int treeSize,
int& kth_smallest)
{
if (root == NULL)
return false;
// Find the median
// (division operation is floored)
int median_loc = (treeSize / 2) + 1;
// If the element is at
// the median
if (k == median_loc)
{
kth_smallest = root->key;
return true;
}
// calculate the number of nodes in the
// right and left sub-trees
// (division operation is floored)
int newTreeSize = treeSize / 2;
// If median is located higher
if (k < median_loc)
{
return KSmallestPerfectBST(
root->left, k,
newTreeSize, kth_smallest);
}
// If median is located lower
int newK = k - median_loc;
return KSmallestPerfectBST(root->right, newK,
newTreeSize,
kth_smallest);
}
// Driver Code
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80
/\ /\ /\ / \
14 25 35 45 55 65 75 85
*/
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);
insert(root, 14);
insert(root, 25);
insert(root, 35);
insert(root, 45);
insert(root, 55);
insert(root, 65);
insert(root, 75);
insert(root, 85);
int n = 15, k = 5;
int ans = -1;
// Function call
if (KSmallestPerfectBST(root, k, n, ans)) {
cout << ans << " ";
}
return 0;
}
Java
// Java program to find K-th
// smallest element in a
// perfect BST
import java.util.*;
class GFG{
// A BST node
static class Node
{
int key;
Node left, right;
};
static int kth_smallest;
// A utility function to
// create a new BST node
public static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a
// new node with given key in BST
static Node insert(Node node, int key)
{
// If the tree is empty
if (node == null)
return newNode(key);
// Recur down the left
// subtree for smaller values
if (key < node.key)
node.left = insert(node.left, key);
// Recur down the right
// subtree for smaller values
else if (key > node.key)
node.right = insert(node.right, key);
// Return the (unchanged) node pointer
return node;
}
// FUnction to find Kth Smallest
// element in a perfect BST
static boolean KSmallestPerfectBST(Node root, int k,
int treeSize)
{
if (root == null)
return false;
// Find the median
// (division operation is floored)
int median_loc = (treeSize / 2) + 1;
// If the element is at
// the median
if (k == median_loc)
{
kth_smallest = root.key;
return true;
}
// calculate the number of nodes in the
// right and left sub-trees
// (division operation is floored)
int newTreeSize = treeSize / 2;
// If median is located higher
if (k < median_loc)
{
return KSmallestPerfectBST(
root.left, k,
newTreeSize);
}
// If median is located lower
int newK = k - median_loc;
return KSmallestPerfectBST(root.right, newK,
newTreeSize);
}
// Driver Code
public static void main(String[] args)
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80
/\ /\ /\ / \
14 25 35 45 55 65 75 85
*/
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);
insert(root, 14);
insert(root, 25);
insert(root, 35);
insert(root, 45);
insert(root, 55);
insert(root, 65);
insert(root, 75);
insert(root, 85);
int n = 15, k = 5;
// Function call
if (KSmallestPerfectBST(root, k, n))
{
System.out.print(kth_smallest + " ");
}
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to find K-th # smallest element in a perfect BST kth_smallest = 0 # A BST node class newNode: def __init__(self, item): self.key = item self.left = None self.right = None # A utility function to insert a # new node with given key in BST def insert(node, key): # If the tree is empty if (node == None): return newNode(key) # Recur down the left # subtree for smaller values if (key < node.key): node.left = insert(node.left, key) # Recur down the right # subtree for smaller values elif(key > node.key): node.right = insert(node.right, key) # Return the (unchanged) node pointer return node # FUnction to find Kth Smallest # element in a perfect BST def KSmallestPerfectBST(root, k, treeSize): global kth_smallest if (root == None): return False # Find the median # (division operation is floored) median_loc = (treeSize // 2) + 1 # If the element is at # the median if (k == median_loc): kth_smallest = root.key return True # Calculate the number of nodes in # the right and left sub-trees # (division operation is floored) newTreeSize = treeSize // 2 # If median is located higher if (k < median_loc): return KSmallestPerfectBST(root.left, k, newTreeSize) # If median is located lower newK = k - median_loc return KSmallestPerfectBST(root.right, newK, newTreeSize) # Driver Code if __name__ == '__main__': ''' Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 /\ /\ /\ / \ 14 25 35 45 55 65 75 85 ''' root = None root = insert(root, 50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root, 80) insert(root, 14) insert(root, 25) insert(root, 35) insert(root, 45) insert(root, 55) insert(root, 65) insert(root, 75) insert(root, 85) n = 15 k = 5 # Function call if (KSmallestPerfectBST(root, k, n)): print(kth_smallest, end = " ") # This code is contributed by ipg2016107
C#
// C# program to find K-th
// smallest element in a
// perfect BST
using System;
class GFG{
// A BST node
public class Node
{
public int key;
public Node left,
right;
};
static int kth_smallest;
// A utility function to
// create a new BST node
public static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// A utility function to
// insert a new node with
// given key in BST
static Node insert(Node node,
int key)
{
// If the tree is empty
if (node == null)
return newNode(key);
// Recur down the left
// subtree for smaller values
if (key < node.key)
node.left = insert(node.left,
key);
// Recur down the right
// subtree for smaller values
else if (key > node.key)
node.right = insert(node.right,
key);
// Return the (unchanged)
// node pointer
return node;
}
// Function to find Kth Smallest
// element in a perfect BST
static bool KSmallestPerfectBST(Node root, int k,
int treeSize)
{
if (root == null)
return false;
// Find the median
// (division operation is floored)
int median_loc = (treeSize / 2) + 1;
// If the element is at
// the median
if (k == median_loc)
{
kth_smallest = root.key;
return true;
}
// calculate the number of nodes
// in the right and left sub-trees
// (division operation is floored)
int newTreeSize = treeSize / 2;
// If median is located higher
if (k < median_loc)
{
return KSmallestPerfectBST(root.left, k,
newTreeSize);
}
// If median is located lower
int newK = k - median_loc;
return KSmallestPerfectBST(root.right, newK,
newTreeSize);
}
// Driver Code
public static void Main(String[] args)
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80
/\ /\ /\ / \
14 25 35 45 55 65 75 85
*/
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);
insert(root, 14);
insert(root, 25);
insert(root, 35);
insert(root, 45);
insert(root, 55);
insert(root, 65);
insert(root, 75);
insert(root, 85);
int n = 15, k = 5;
// Function call
if (KSmallestPerfectBST(root,
k, n))
{
Console.Write(kth_smallest + " ");
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find K-th
// smallest element in a
// perfect BST
// A BST node
class Node
{
constructor()
{
this.key = 0;
this.left = null;
this.right = null;
}
};
var kth_smallest;
// A utility function to
// create a new BST node
function newNode(item)
{
var temp = new Node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// A utility function to
// insert a new node with
// given key in BST
function insert( node, key)
{
// If the tree is empty
if (node == null)
return newNode(key);
// Recur down the left
// subtree for smaller values
if (key < node.key)
node.left = insert(node.left,
key);
// Recur down the right
// subtree for smaller values
else if (key > node.key)
node.right = insert(node.right,
key);
// Return the (unchanged)
// node pointer
return node;
}
// Function to find Kth Smallest
// element in a perfect BST
function KSmallestPerfectBST(root, k, treeSize)
{
if (root == null)
return false;
// Find the median
// (division operation is floored)
var median_loc = parseInt(treeSize / 2) + 1;
// If the element is at
// the median
if (k == median_loc)
{
kth_smallest = root.key;
return true;
}
// calculate the number of nodes
// in the right and left sub-trees
// (division operation is floored)
var newTreeSize = parseInt(treeSize / 2);
// If median is located higher
if (k < median_loc)
{
return KSmallestPerfectBST(root.left, k,
newTreeSize);
}
// If median is located lower
var newK = k - median_loc;
return KSmallestPerfectBST(root.right, newK,
newTreeSize);
}
// Driver Code
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80
/\ /\ /\ / \
14 25 35 45 55 65 75 85
*/
var root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
insert(root, 14);
insert(root, 25);
insert(root, 35);
insert(root, 45);
insert(root, 55);
insert(root, 65);
insert(root, 75);
insert(root, 85);
var n = 15, k = 5;
// Function call
if (KSmallestPerfectBST(root,
k, n))
{
document.write(kth_smallest + " ");
}
// This code is contributed by rrrtnx.
</script>
Producción
35
Complejidad temporal: O(Log(N))
Espacio auxiliar: O(Log(N))