Dado un árbol de búsqueda binario (BST) con duplicados, encuentre el Node (el elemento que ocurre con más frecuencia) en el BST dado. Si el BST contiene dos o más de estos Nodes, imprima cualquiera de ellos.
Nota: No podemos utilizar ningún espacio adicional. (Suponga que el espacio de pila implícito incurrido debido a la recursividad no cuenta)
Suponga que un BST se define de la siguiente manera:
- El subárbol izquierdo de un Node contiene solo Nodes con claves menores o iguales a la clave del Node.
- El subárbol derecho de un Node contiene solo Nodes con claves mayores o iguales que la clave del Node.
- Los subárboles izquierdo y derecho también deben ser árboles de búsqueda binarios.
Ejemplos:
Input : Given BST is
6
/ \
5 7
/ \ / \
4 5 7 7
Output : 7
Input : Given BST is
10
/ \
5 12
/ \ / \
5 6 12 16
Output : 5 or 12
We can print any of the two value 5 or 12.
Enfoque:
para encontrar el Node, necesitamos encontrar el recorrido en orden del BST porque su recorrido en orden estará ordenado.
Entonces, la idea es hacer un recorrido Inorder recursivo y mantener el seguimiento del Node anterior. Si el valor del Node actual es igual al valor anterior, podemos aumentar el conteo actual y si el conteo actual es mayor que el conteo máximo, reemplace el elemento.
A continuación se muestra la implementación del enfoque anterior:
C++
/* C++ program to find the median of BST in O(n)
time and O(1) space*/
#include <iostream>
using namespace std;
/* A binary search tree Node has data, pointer
to left child and a pointer to right child */
struct Node {
int val;
struct Node *left, *right;
};
struct Node* newNode(int data)
{
struct Node* temp = new Node;
temp->val = data;
temp->left = temp->right = NULL;
return temp;
}
// cur for storing the current count of the value
// and mx for the maximum count of the element which is denoted by node
int cur = 1, mx = 0;
int node;
struct Node* previous = NULL;
// Find the inorder traversal of the BST
void inorder(struct Node* root)
{
// If root is NULL then return
if (root == NULL) {
return;
}
inorder(root->left);
if (previous != NULL) {
// If the previous value is equal to the current value
// then increase the count
if (root->val == previous->val) {
cur++;
}
// Else initialize the count by 1
else {
cur = 1;
}
}
// If current count is greater than the max count
// then update the mx value
if (cur > mx) {
mx = cur;
node = root->val;
}
// Make the current Node as previous
previous = root;
inorder(root->right);
}
// Utility function
int findnode(struct Node* root)
{
inorder(root);
return node;
}
int main()
{
/* Let us create following BST
6
/ \
5 7
/ \ / \
4 5 7 7
*/
struct Node* root = newNode(6);
root->left = newNode(5);
root->right = newNode(7);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(7);
root->right->right = newNode(7);
cout << "Node of BST is " << findnode(root) << '\n';
return 0;
}
Java
/* Java program to find the median of BST
in O(n) time and O(1) space*/
class GFG
{
/* A binary search tree Node has data, pointer
to left child and a pointer to right child */
static class Node
{
int val;
Node left, right;
};
static Node newNode(int data)
{
Node temp = new Node();
temp.val = data;
temp.left = temp.right = null;
return temp;
}
// cur for storing the current count
// of the value and mx for the maximum count
// of the element which is denoted by node
static int cur = 1, mx = 0;
static int node;
static Node previous = null;
// Find the inorder traversal of the BST
static void inorder(Node root)
{
// If root is null then return
if (root == null)
{
return;
}
inorder(root.left);
if (previous != null)
{
// If the previous value is equal to
// the current value then increase the count
if (root.val == previous.val)
{
cur++;
}
// Else initialize the count by 1
else
{
cur = 1;
}
}
// If current count is greater than the
// max count then update the mx value
if (cur > mx)
{
mx = cur;
node = root.val;
}
// Make the current Node as previous
previous = root;
inorder(root.right);
}
// Utility function
static int findnode(Node root)
{
inorder(root);
return node;
}
// Java Code
public static void main(String args[])
{
/* Let us create following BST
6
/ \
5 7
/ \ / \
4 5 7 7
*/
Node root = newNode(6);
root.left = newNode(5);
root.right = newNode(7);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.left = newNode(7);
root.right.right = newNode(7);
System.out.println("Node of BST is " +
findnode(root));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python program to find the median of BST
# in O(n) time and O(1) space
# A binary search tree Node has data, pointer
# to left child and a pointer to right child
class Node:
def __init__(self):
self.val = 0
self.left = None
self.right = None
def newNode(data: int) -> Node:
temp = Node()
temp.val = data
temp.left = temp.right = None
return temp
# cur for storing the current count
# of the value and mx for the maximum count
# of the element which is denoted by node
cur = 1
mx = 0
node = 0
previous = Node()
# Find the inorder traversal of the BST
def inorder(root: Node):
global cur, mx, node, previous
# If root is null then return
if root is None:
return
inorder(root.left)
if previous is not None:
# If the previous value is equal to
# the current value then increase the count
if root.val == previous.val:
cur += 1
# Else initialize the count by 1
else:
cur = 1
# If current count is greater than the
# max count then update the mx value
if cur > mx:
mx = cur
node = root.val
# Make the current Node as previous
previous = root
inorder(root.right)
# Utility function
def findNode(root: Node) -> int:
global node
inorder(root)
return node
# Driver Code
if __name__ == "__main__":
# Let us create following BST
# 6
# / \
# 5 7
# / \ / \
# 4 5 7 7
root = newNode(6)
root.left = newNode(5)
root.right = newNode(7)
root.left.left = newNode(4)
root.left.right = newNode(5)
root.right.left = newNode(7)
root.right.right = newNode(7)
print("Node of BST is", findNode(root))
# This code is contributed by
# sanjeev2552
C#
/* C# program to find the median of BST
in O(n) time and O(1) space*/
using System;
class GFG
{
/* A binary search tree Node has data, pointer
to left child and a pointer to right child */
public class Node
{
public int val;
public Node left, right;
};
static Node newNode(int data)
{
Node temp = new Node();
temp.val = data;
temp.left = temp.right = null;
return temp;
}
// cur for storing the current count
// of the value and mx for the maximum count
// of the element which is denoted by node
static int cur = 1, mx = 0;
static int node;
static Node previous = null;
// Find the inorder traversal of the BST
static void inorder(Node root)
{
// If root is null then return
if (root == null)
{
return;
}
inorder(root.left);
if (previous != null)
{
// If the previous value is equal to
// the current value then increase the count
if (root.val == previous.val)
{
cur++;
}
// Else initialize the count by 1
else
{
cur = 1;
}
}
// If current count is greater than the
// max count then update the mx value
if (cur > mx)
{
mx = cur;
node = root.val;
}
// Make the current Node as previous
previous = root;
inorder(root.right);
}
// Utility function
static int findnode(Node root)
{
inorder(root);
return node;
}
// Driver Code
public static void Main(String []args)
{
/* Let us create following BST
6
/ \
5 7
/ \ / \
4 5 7 7
*/
Node root = newNode(6);
root.left = newNode(5);
root.right = newNode(7);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.left = newNode(7);
root.right.right = newNode(7);
Console.WriteLine("Node of BST is " +
findnode(root));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
/* Javascript program to find the median of BST
in O(n) time and O(1) space*/
/* A binary search tree Node has data, pointer
to left child and a pointer to right child */
class Node
{
constructor()
{
this.val = 0;
this.left = null;
this.right = null;
}
};
function newNode(data)
{
var temp = new Node();
temp.val = data;
temp.left = temp.right = null;
return temp;
}
// cur for storing the current count
// of the value and mx for the maximum count
// of the element which is denoted by node
var cur = 1, mx = 0;
var node;
var previous = null;
// Find the inorder traversal of the BST
function inorder(root)
{
// If root is null then return
if (root == null)
{
return;
}
inorder(root.left);
if (previous != null)
{
// If the previous value is equal to
// the current value then increase the count
if (root.val == previous.val)
{
cur++;
}
// Else initialize the count by 1
else
{
cur = 1;
}
}
// If current count is greater than the
// max count then update the mx value
if (cur > mx)
{
mx = cur;
node = root.val;
}
// Make the current Node as previous
previous = root;
inorder(root.right);
}
// Utility function
function findnode(root)
{
inorder(root);
return node;
}
// Driver Code
/* Let us create following BST
6
/ \
5 7
/ \ / \
4 5 7 7
*/
var root = newNode(6);
root.left = newNode(5);
root.right = newNode(7);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.left = newNode(7);
root.right.right = newNode(7);
document.write("Node of BST is " +
findnode(root));
// This code is contributed by noob2000.
</script>
Producción:
node of BST is 7
Complejidad temporal: 
Espacio auxiliar : O(N).
Publicación traducida automáticamente
Artículo escrito por ojas_bansal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA