Tenemos un árbol de búsqueda binaria y un número N. Nuestra tarea es encontrar el mayor número en el árbol de búsqueda binaria que sea menor o igual a N. Imprime el valor del elemento si existe, de lo contrario imprime -1.
C++
// C++ code to find the largest value smaller
// than or equal to N
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
Node *left, *right;
};
// To create new BST Node
Node* newNode(int item)
{
Node* temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// To insert a new node in BST
Node* insert(Node* node, int key)
{
// if tree is empty return new node
if (node == NULL)
return newNode(key);
// if key is less than or greater than
// node value then 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;
}
// Returns largest value smaller than or equal to
// key. If key is smaller than the smallest, it
// returns -1.
int findFloor(Node* root, int key)
{
Node *curr = root, *ans = NULL;
while (curr) {
if (curr->key <= key) {
ans = curr;
curr = curr->right;
}
else
curr = curr->left;
}
if (ans)
return ans->key;
return -1;
}
// Driver code
int main()
{
int N = 25;
Node* root = insert(root, 19);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 12);
insert(root, 9);
insert(root, 21);
insert(root, 19);
insert(root, 25);
printf("%d", findFloor(root, N));
return 0;
}
Java
// Java code to find the largest value smaller
// than or equal to N
class GFG
{
static class Node
{
int key;
Node left, right;
};
// To create new BST Node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// To insert a new node in BST
static Node insert(Node node, int key)
{
// if tree is empty return new node
if (node == null)
return newNode(key);
// if key is less than or greater than
// node value then 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;
}
// Returns largest value smaller than or equal to
// key. If key is smaller than the smallest, it
// returns -1.
static int findFloor(Node root, int key)
{
Node curr = root, ans = null;
while (curr != null)
{
if (curr.key <= key)
{
ans = curr;
curr = curr.right;
}
else
curr = curr.left;
}
if (ans != null)
return ans.key;
return -1;
}
// Driver code
public static void main(String[] args)
{
int N = 25;
Node root = new Node();
insert(root, 19);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 12);
insert(root, 9);
insert(root, 21);
insert(root, 19);
insert(root, 25);
System.out.printf("%d", findFloor(root, N));
}
}
/* This code is contributed by PrinciRaj1992 */
Python3
# Python3 code to find the largest value # smaller than or equal to N class newNode: def __init__(self, item): self.key = item self.left = None self.right = None # To insert a new node in BST def insert(node, key): # If tree is empty return new node if (node == None): return newNode(key) # If key is less than or greater than # node value then 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 # Returns largest value smaller than or # equal to key. If key is smaller than # the smallest, it returns -1. def findFloor(root, key): curr = root ans = None while (curr): if (curr.key <= key): ans = curr curr = curr.right else: curr = curr.left if (ans): return ans.key return -1 # Driver code if __name__ == '__main__': N = 25 root = None root = insert(root, 19) insert(root, 2) insert(root, 1) insert(root, 3) insert(root, 12) insert(root, 9) insert(root, 21) insert(root, 19) insert(root, 25) print(findFloor(root, N)) # This code is contributed by bgangwar59
C#
// C# code to find the largest value smaller
// than or equal to N
using System;
using System.Collections.Generic;
class GFG
{
public class Node
{
public int key;
public Node left, right;
};
// To create new BST Node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// To insert a new node in BST
static Node insert(Node node, int key)
{
// if tree is empty return new node
if (node == null)
return newNode(key);
// if key is less than or greater than
// node value then 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;
}
// Returns largest value smaller than or equal to
// key. If key is smaller than the smallest, it
// returns -1.
static int findFloor(Node root, int key)
{
Node curr = root, ans = null;
while (curr != null)
{
if (curr.key <= key)
{
ans = curr;
curr = curr.right;
}
else
curr = curr.left;
}
if (ans != null)
return ans.key;
return -1;
}
// Driver code
public static void Main(String[] args)
{
int N = 25;
Node root = new Node();
insert(root, 19);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 12);
insert(root, 9);
insert(root, 21);
insert(root, 19);
insert(root, 25);
Console.Write("{0}", findFloor(root, N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript code to find the largest
// value smaller than or equal to N
class Node
{
constructor(item)
{
this.key = item;
this.left = null;
this.right = null;
}
}
// To create new BST Node
function newNode(item)
{
let temp = new Node(item);
return temp;
}
// To insert a new node in BST
function insert(node, key)
{
// If tree is empty return new node
if (node == null)
return newNode(key);
// If key is less than or greater than
// node value then 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;
}
// Returns largest value smaller than or
// equal to key. If key is smaller than
// the smallest, it returns -1.
function findFloor(root, key)
{
let curr = root, ans = null;
while (curr != null)
{
if (curr.key <= key)
{
ans = curr;
curr = curr.right;
}
else
curr = curr.left;
}
if (ans != null)
return ans.key;
return -1;
}
// Driver code
let N = 25;
let root = new Node(N);
insert(root, 19);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 12);
insert(root, 9);
insert(root, 21);
insert(root, 19);
insert(root, 25);
document.write(findFloor(root, N));
// This code is contributed by divyeshrabadiya07
</script>