Dado un árbol de búsqueda binario que contiene valores enteros positivos mayores que 0, la tarea es verificar si el BST contiene un callejón sin salida o no. Aquí Dead End significa que no podemos insertar ningún elemento entero después de ese Node.
Ejemplos:
Input : 8
/ \
5 9
/ \
2 7
/
1
Output : Yes
Explanation : Node "1" is the dead End because
after that we cant insert any element.
Input : 8
/ \
7 10
/ / \
2 9 13
Output :Yes
Explanation : We can't insert any element at
node 9.
Hemos discutido una solución en la publicación a continuación.
Comprobar si BST contiene Dead End o no
La idea de este artículo se basa en el método 3 de Comprobar si un árbol binario es BST o no .
En primer lugar, se da que es un BST y los Nodes son mayores que cero, el Node raíz puede estar en el rango [1, ∞] y si el valor raíz es, digamos, valor, entonces el subárbol izquierdo puede tener el valor en el rango [1, val-1] y el subárbol derecho el valor en el rango [val+1, ∞].
necesitamos atravesar recursivamente y cuando el valor mínimo y máximo del rango coincidieron, significa que no podemos agregar ningún Node más en el árbol.
Por lo tanto, nos encontramos con un callejón sin salida.
A continuación se muestra la solución recursiva simple al problema.
C++
// CPP Program to check if there is a dead end
// in BST or not.
#include <bits/stdc++.h>
using namespace std;
// A BST node
struct Node {
int data;
struct Node *left, *right;
};
// A utility function to create a new node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
/* A utility function to insert a new Node
with given key in BST */
struct Node* insert(struct 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->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
/* return the (unchanged) Node pointer */
return node;
}
// Returns true if tree with given root contains
// dead end or not. min and max indicate range
// of allowed values for current node. Initially
// these values are full range.
bool deadEnd(Node* root, int min=1, int max=INT_MAX)
{
// if the root is null or the recursion moves
// after leaf node it will return false
// i.e no dead end.
if (!root)
return false;
// if this occurs means dead end is present.
if (min == max)
return true;
// heart of the recursion lies here.
return deadEnd(root->left, min, root->data - 1) ||
deadEnd(root->right, root->data + 1, max);
}
// Driver program
int main()
{
/* 8
/ \
5 11
/ \
2 7
\
3
\
4 */
Node* root = NULL;
root = insert(root, 8);
root = insert(root, 5);
root = insert(root, 2);
root = insert(root, 3);
root = insert(root, 7);
root = insert(root, 11);
root = insert(root, 4);
if (deadEnd(root) == true)
cout << "Yes " << endl;
else
cout << "No " << endl;
return 0;
}
Java
// Java Program to check if there
// is a dead end in BST or not.
class BinarySearchTree {
// Class containing left and right
// child of current node and key value
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// This method mainly calls insertRec()
void insert(int data) {
root = insertRec(root, data);
}
// A recursive function
// to insert a new key in BST
Node insertRec(Node root, int data) {
// If the tree is empty,
// return a new node
if (root == null) {
root = new Node(data);
return root;
}
/* Otherwise, recur down the tree */
if (data < root.data)
root.left = insertRec(root.left, data);
else if (data > root.data)
root.right = insertRec(root.right, data);
/* return the (unchanged) node pointer */
return root;
}
// Returns true if tree with given root contains
// dead end or not. min and max indicate range
// of allowed values for current node. Initially
// these values are full range.
boolean deadEnd(Node root, int min, int max)
{
// if the root is null or the recursion moves
// after leaf node it will return false
// i.e no dead end.
if (root==null)
return false;
// if this occurs means dead end is present.
if (min == max)
return true;
// heart of the recursion lies here.
return deadEnd(root.left, min, root.data - 1)||
deadEnd(root.right, root.data + 1, max);
}
// Driver Program
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
/* 8
/ \
5 11
/ \
2 7
\
3
\
4 */
tree.insert(8);
tree.insert(5);
tree.insert(2);
tree.insert(3);
tree.insert(7);
tree.insert(11);
tree.insert(4);
if (tree.deadEnd(tree.root ,1 ,
Integer.MAX_VALUE) == true)
System.out.println("Yes ");
else
System.out.println("No " );
}
}
// This code is contributed by Gitanjali.
Python3
# Python 3 Program to check if there
# is a dead end in BST or not.
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
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,
# return a new Node
if node == None:
return Node(key)
# Otherwise, recur down the tree
if key < node.data:
node.left = insert(node.left, key)
elif key > node.data:
node.right = insert(node.right, key)
# return the (unchanged) Node pointer
return node
# Returns true if tree with given
# root contains dead end or not.
# min and max indicate range
# of allowed values for current node.
# Initially these values are full range.
def deadEnd(root, Min, Max):
# if the root is null or the recursion
# moves after leaf node it will return
# false i.e no dead end.
if root == None:
return False
# if this occurs means dead
# end is present.
if Min == Max:
return True
# heart of the recursion lies here.
return (deadEnd(root.left, Min, root.data - 1) or
deadEnd(root.right, root.data + 1, Max))
# Driver Code
if __name__ == '__main__':
# 8
# / \
# 5 11
# / \
# 2 7
# \
# 3
# \
# 4
root = None
root = insert(root, 8)
root = insert(root, 5)
root = insert(root, 2)
root = insert(root, 3)
root = insert(root, 7)
root = insert(root, 11)
root = insert(root, 4)
if deadEnd(root, 1, 9999999999) == True:
print("Yes")
else:
print("No")
# This code is contributed by PranchalK
C#
using System;
// C# Program to check if there
// is a dead end in BST or not.
public class BinarySearchTree
{
// Class containing left and right
// child of current node and key value
public class Node
{
private readonly BinarySearchTree outerInstance;
public int data;
public Node left, right;
public Node(BinarySearchTree outerInstance, int item)
{
this.outerInstance = outerInstance;
data = item;
left = right = null;
}
}
// Root of BST
public Node root;
// Constructor
public BinarySearchTree()
{
root = null;
}
// This method mainly calls insertRec()
public virtual void insert(int data)
{
root = insertRec(root, data);
}
// A recursive function
// to insert a new key in BST
public virtual Node insertRec(Node root, int data)
{
// If the tree is empty,
// return a new node
if (root == null)
{
root = new Node(this, data);
return root;
}
/* Otherwise, recur down the tree */
if (data < root.data)
{
root.left = insertRec(root.left, data);
}
else if (data > root.data)
{
root.right = insertRec(root.right, data);
}
/* return the (unchanged) node pointer */
return root;
}
// Returns true if tree with given root contains
// dead end or not. min and max indicate range
// of allowed values for current node. Initially
// these values are full range.
public virtual bool deadEnd(Node root, int min, int max)
{
// if the root is null or the recursion moves
// after leaf node it will return false
// i.e no dead end.
if (root == null)
{
return false;
}
// if this occurs means dead end is present.
if (min == max)
{
return true;
}
// heart of the recursion lies here.
return deadEnd(root.left, min, root.data - 1) || deadEnd(root.right, root.data + 1, max);
}
// Driver Program
public static void Main(string[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* 8
/ \
5 11
/ \
2 7
\
3
\
4 */
tree.insert(8);
tree.insert(5);
tree.insert(2);
tree.insert(3);
tree.insert(7);
tree.insert(11);
tree.insert(4);
if (tree.deadEnd(tree.root,1, int.MaxValue) == true)
{
Console.WriteLine("Yes ");
}
else
{
Console.WriteLine("No ");
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// javascript Program to check if there
// is a dead end in BST or not.
// Class containing left and right
// child of current node and key value
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
// Root of BST
var root = null;
// This method mainly calls insertRec()
function insert(data) {
root = insertRec(root, data);
}
// A recursive function
// to insert a new key in BST
function insertRec(root , data) {
// If the tree is empty,
// return a new node
if (root == null) {
root = new Node(data);
return root;
}
/* Otherwise, recur down the tree */
if (data < root.data)
root.left = insertRec(root.left, data);
else if (data > root.data)
root.right = insertRec(root.right, data);
/* return the (unchanged) node pointer */
return root;
}
// Returns true if tree with given root contains
// dead end or not. min and max indicate range
// of allowed values for current node. Initially
// these values are full range.
function deadEnd(root , min , max)
{
// if the root is null or the recursion moves
// after leaf node it will return false
// i.e no dead end.
if (root==null)
return false;
// if this occurs means dead end is present.
if (min == max)
return true;
// heart of the recursion lies here.
return deadEnd(root.left, min, root.data - 1)||
deadEnd(root.right, root.data + 1, max);
} // Driver Program
/* 8
/ \
5 11
/ \
2 7
\
3
\
4 */
insert(8);
insert(5);
insert(2);
insert(3);
insert(7);
insert(11);
insert(4);
if (deadEnd(root ,1 ,
Number.MAX_VALUE) == true)
document.write("Yes ");
else
document.write("No " );
// This code contributed by Rajput-Ji
</script>
Producción:
Yes
Publicación traducida automáticamente
Artículo escrito por vishal22091998 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA