Número más pequeño en BST que es mayor o igual a N – Part 1

Posted on by Rudeus Greyrat

Dado un árbol de búsqueda binaria y un número N, la tarea es encontrar el número más pequeño en el árbol de búsqueda binaria que sea mayor o igual a N. Imprime el valor del elemento si existe; de ​​lo contrario, imprime -1.
 

 

Ejemplos: 

Entrada: N = 20 
Salida: 21 
Explicación: 21 es el elemento más pequeño mayor que 20.

Entrada: N = 18 
Salida: 19 
Explicación: 19 es el elemento más pequeño mayor que 18. 
 

Enfoque: 
La idea es seguir el enfoque recursivo para resolver el problema, es decir, comenzar a buscar el elemento desde la raíz. 

  • Si hay un Node hoja que tiene un valor menor que N, entonces el elemento no existe y devuelve -1.
  • De lo contrario, si el valor del Node es mayor o igual a N y el hijo izquierdo es NULL o menor que N, devuelva el valor del Node.
  • De lo contrario, si el valor del Node es menor que N, busque el elemento en el subárbol derecho.
  • De lo contrario, busque el elemento en el subárbol izquierdo llamando a la función recursivamente según el valor izquierdo o derecho.

C++

// C++ program to find the smallest value
// greater than or equal to N
#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int data;
    Node *left, *right;
};
 
// To create new BST Node
Node* createNode(int item)
{
    Node* temp = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
 
    return temp;
}
 
// To add a new node in BST
Node* add(Node* node, int key)
{
    // if tree is empty return new node
    if (node == NULL)
        return createNode(key);
 
    // if key is less than or greater than
    // node value then recur down the tree
    if (key < node->data)
        node->left = add(node->left, key);
    else if (key > node->data)
        node->right = add(node->right, key);
 
    // return the (unchanged) node pointer
    return node;
}
 
// function to find min value less than N
int findMinforN(Node* root, int N)
{
    // If leaf node reached and is smaller than N
    if (root->left == NULL && root->right == NULL
                                && root->data < N)
        return -1;
 
    // If node's value is greater than N and left value
    // is NULL or smaller then return the node value
    if ((root->data >= N && root->left == NULL)
        || (root->data >= N && root->left->data < N))
        return root->data;
 
    // if node value is smaller than N search in the
    // right subtree
    if (root->data <= N)
        return findMinforN(root->right, N);
 
    // if node value is greater than N search in the
    // left subtree
    else
        return findMinforN(root->left, N);
}
 
// Drivers code
int main()
{
    /*    19
        /    \
       7     21
     /   \
    3     11
         /   \
         9    14
          */
 
    Node* root = NULL;
    root = add(root, 19);
    root = add(root, 7);
    root = add(root, 3);
    root = add(root, 11);
    root = add(root, 9);
    root = add(root, 13);
    root = add(root, 21);
 
    int N = 18;
    cout << findMinforN(root, N) << endl;
 
    return 0;
}

Java

// Java program to find the smallest value
// greater than or equal to N
import java.util.*;
class GFG
{
static class Node
{
    int data;
    Node left, right;
};
 
// To create new BST Node
static Node createNode(int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.left = temp.right = null;
 
    return temp;
}
 
// To add a new node in BST
static Node add(Node node, int key)
{
    // if tree is empty return new node
    if (node == null)
        return createNode(key);
 
    // if key is less than or greater than
    // node value then recur down the tree
    if (key < node.data)
        node.left = add(node.left, key);
    else if (key > node.data)
        node.right = add(node.right, key);
 
    // return the (unchanged) node pointer
    return node;
}
 
// function to find min value less than N
static int findMinforN(Node root, int N)
{
    // If leaf node reached and is smaller than N
    if (root.left == null &&
        root.right == null && root.data < N)
        return -1;
 
    // If node's value is greater than N and left value
    // is null or smaller then return the node value
    if ((root.data >= N && root.left == null) ||
        (root.data >= N && root.left.data < N))
        return root.data;
 
    // if node value is smaller than N search in the
    // right subtree
    if (root.data <= N)
        return findMinforN(root.right, N);
 
    // if node value is greater than N search in the
    // left subtree
    else
        return findMinforN(root.left, N);
}
 
// Driver Code
public static void main(String[] args)
{
    /* 19
        / \
    7     21
    / \
    3     11
        / \
        9 14
        */
 
    Node root = null;
    root = add(root, 19);
    root = add(root, 7);
    root = add(root, 3);
    root = add(root, 11);
    root = add(root, 9);
    root = add(root, 13);
    root = add(root, 21);
 
    int N = 18;
    System.out.println(findMinforN(root, N));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python program to find the smallest value
# greater than or equal to N
 
class Node:
    def __init__(self):
        self.data = 0
        self.left = None
        self.right = None
 
# To create new BST Node
def createNode(item: int):
    temp = Node()
    temp.data = item
    temp.left = temp.right = None
    return temp
 
# To add a new node in BST
def add(node: Node, key: int):
 
    # if tree is empty return new node
    if node is None:
        return createNode(key)
 
    # if key is less than or greater than
    # node value then recur down the tree
    if key < node.data:
        node.left = add(node.left, key)
    elif key > node.data:
        node.right = add(node.right, key)
 
    # return the (unchanged) node pointer
    return node
 
# function to find min value less than N
def findMinforN(root: Node, N: int):
 
    # If leaf node reached and is smaller than N
    if root.left is None and root.right is None and root.data < N:
        return -1
 
    # If node's value is greater than N and left value
    # is NULL or smaller then return the node value
    if root.data >= N and root.left is None or root.data >= N and root.left.data < N:
        return root.data
 
    # if node value is smaller than N search in the
    # right subtree
    if root.data <= N:
        return findMinforN(root.right, N)
 
    # if node value is greater than N search in the
    # left subtree
    else:
        return findMinforN(root.left, N)
 
# Driver Code
if __name__ == "__main__":
 
    '''
            19
        / \
        7     21
        / \
    3 11
        / \
        9 14
    '''
    root = Node()
    root = add(root, 19)
    root = add(root, 7)
    root = add(root, 3)
    root = add(root, 11)
    root = add(root, 9)
    root = add(root, 13)
    root = add(root, 21)
 
    N = 18
    print(findMinforN(root, N))
 
# This code is contributed by
# sanjeev2552

C#

// C# program to find the smallest value
// greater than or equal to N
using System;
 
class GFG
{
class Node
{
    public int data;
    public Node left, right;
};
 
// To create new BST Node
static Node createNode(int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.left = temp.right = null;
 
    return temp;
}
 
// To add a new node in BST
static Node add(Node node, int key)
{
    // if tree is empty return new node
    if (node == null)
        return createNode(key);
 
    // if key is less than or greater than
    // node value then recur down the tree
    if (key < node.data)
        node.left = add(node.left, key);
    else if (key > node.data)
        node.right = add(node.right, key);
 
    // return the (unchanged) node pointer
    return node;
}
 
// function to find min value less than N
static int findMinforN(Node root, int N)
{
    // If leaf node reached and is smaller than N
    if (root.left == null &&
        root.right == null && root.data < N)
        return -1;
 
    // If node's value is greater than N and left value
    // is null or smaller then return the node value
    if ((root.data >= N && root.left == null) ||
        (root.data >= N && root.left.data < N))
        return root.data;
 
    // if node value is smaller than N search in the
    // right subtree
    if (root.data <= N)
        return findMinforN(root.right, N);
 
    // if node value is greater than N search in the
    // left subtree
    else
        return findMinforN(root.left, N);
}
 
// Driver Code
public static void Main(String[] args)
{
    /* 19
        / \
    7     21
    / \
    3     11
        / \
        9 14
        */
 
    Node root = null;
    root = add(root, 19);
    root = add(root, 7);
    root = add(root, 3);
    root = add(root, 11);
    root = add(root, 9);
    root = add(root, 13);
    root = add(root, 21);
 
    int N = 18;
    Console.WriteLine(findMinforN(root, N));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// javascript program to find the smallest value
// greater than or equal to N
 
class Node
{
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
};
 
// To create new BST Node
function createNode(item)
{
    var temp = new Node();
    temp.data = item;
    temp.left = temp.right = null;
 
    return temp;
}
 
// To add a new node in BST
function add(node, key)
{
    // if tree is empty return new node
    if (node == null)
        return createNode(key);
 
    // if key is less than or greater than
    // node value then recur down the tree
    if (key < node.data)
        node.left = add(node.left, key);
    else if (key > node.data)
        node.right = add(node.right, key);
 
    // return the (unchanged) node pointer
    return node;
}
 
// function to find min value less than N
function findMinforN(root, N)
{
    // If leaf node reached and is smaller than N
    if (root.left == null &&
        root.right == null && root.data < N)
        return -1;
 
    // If node's value is greater than N and left value
    // is null or smaller then return the node value
    if ((root.data >= N && root.left == null) ||
        (root.data >= N && root.left.data < N))
        return root.data;
 
    // if node value is smaller than N search in the
    // right subtree
    if (root.data <= N)
        return findMinforN(root.right, N);
 
    // if node value is greater than N search in the
    // left subtree
    else
        return findMinforN(root.left, N);
}
 
// Driver Code
/* 19
    / \
7     21
/ \
3     11
    / \
    9 14
    */
var root = null;
root = add(root, 19);
root = add(root, 7);
root = add(root, 3);
root = add(root, 11);
root = add(root, 9);
root = add(root, 13);
root = add(root, 21);
var N = 18;
document.write(findMinforN(root, N));
 
// This code is contributed by famously.
</script>
Producción: 

19

 

Publicación traducida automáticamente

Artículo escrito por akash1295 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 *