Dada una array de tamaño n, la tarea es encontrar si la array puede representar un BST con n niveles.
Como los niveles son n, construimos un árbol de la siguiente manera.
Suponiendo un número X,
- El número mayor que X está en el lado derecho
- El número inferior a X está en el lado izquierdo.
Nota: durante la inserción, nunca vamos más allá de un número ya visitado.
Ejemplos:
Input : 500, 200, 90, 250, 100 Output : No Input : 5123, 3300, 783, 1111, 890 Output : Yes
Explicación :
Para la secuencia 500, 200, 90, 250, 100, el árbol formado (en la imagen de arriba) no puede representar BST.
La secuencia 5123, 3300, 783, 1111, 890 forma un árbol de búsqueda binario, por lo que es una secuencia correcta.
Método 1: Al construir BST
Primero insertamos todos los valores de array nivel por nivel en un árbol. Para insertar, verificamos si el valor actual es menor que el valor anterior o mayor. Después de construir el árbol, verificamos si el árbol construido es un árbol de búsqueda binaria o no.
C++
// C++ program to Check given array
// can represent BST or not
#include <bits/stdc++.h>
using namespace std;
// structure for Binary Node
struct Node {
int key;
struct Node *right, *left;
};
Node* newNode(int num)
{
Node* temp = new Node;
temp->key = num;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// To create a Tree with n levels. We always
// insert new node to left if it is less than
// previous value.
Node* createNLevelTree(int arr[], int n)
{
Node* root = newNode(arr[0]);
Node* temp = root;
for (int i = 1; i < n; i++) {
if (temp->key > arr[i]) {
temp->left = newNode(arr[i]);
temp = temp->left;
}
else {
temp->right = newNode(arr[i]);
temp = temp->right;
}
}
return root;
}
// Please refer below post for details of this
// function.
// https:// www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
bool isBST(Node* root, int min, int max)
{
if (root == NULL)
return true;
if (root->key < min || root->key > max)
return false;
// Allow only distinct values
return (isBST(root->left, min,
(root->key) - 1)
&& isBST(root->right,
(root->key) + 1, max));
}
// Returns tree if given array of size n can
// represent a BST of n levels.
bool canRepresentNLevelBST(int arr[], int n)
{
Node* root = createNLevelTree(arr, n);
return isBST(root, INT_MIN, INT_MAX);
}
// Driver code
int main()
{
int arr[] = { 512, 330, 78, 11, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
if (canRepresentNLevelBST(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to Check given array
// can represent BST or not
class GFG
{
// structure for Binary Node
static class Node
{
int key;
Node right, left;
};
static Node newNode(int num)
{
Node temp = new Node();
temp.key = num;
temp.left = null;
temp.right = null;
return temp;
}
// To create a Tree with n levels. We always
// insert new node to left if it is less than
// previous value.
static Node createNLevelTree(int arr[], int n)
{
Node root = newNode(arr[0]);
Node temp = root;
for (int i = 1; i < n; i++)
{
if (temp.key > arr[i])
{
temp.left = newNode(arr[i]);
temp = temp.left;
}
else
{
temp.right = newNode(arr[i]);
temp = temp.right;
}
}
return root;
}
// Please refer below post for details of this
// function.
// https:// www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
static boolean isBST(Node root, int min, int max)
{
if (root == null)
{
return true;
}
if (root.key < min || root.key > max)
{
return false;
}
// Allow only distinct values
return (isBST(root.left, min,
(root.key) - 1)
&& isBST(root.right,
(root.key) + 1, max));
}
// Returns tree if given array of size n can
// represent a BST of n levels.
static boolean canRepresentNLevelBST(int arr[], int n)
{
Node root = createNLevelTree(arr, n);
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
// Driver code
public static void main(String[] args)
{
int arr[] = {512, 330, 78, 11, 8};
int n = arr.length;
if (canRepresentNLevelBST(arr, n))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
/* This code contributed by PrinciRaj1992 */
Python
# Python program to Check given array
# can represent BST or not
# A binary tree node has data,
# left child and right child
class newNode():
def __init__(self, data):
self.key = data
self.left = None
self.right = None
# To create a Tree with n levels. We always
# insert new node to left if it is less than
# previous value.
def createNLevelTree(arr, n):
root = newNode(arr[0])
temp = root
for i in range(1, n):
if (temp.key > arr[i]):
temp.left = newNode(arr[i])
temp = temp.left
else:
temp.right = newNode(arr[i])
temp = temp.right
return root
# Please refer below post for details of this
# function.
# https:# www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
def isBST(root, min, max):
if (root == None):
return True
if (root.key < min or root.key > max):
return False
# Allow only distinct values
return (isBST(root.left, min, (root.key) - 1) and
isBST(root.right,(root.key) + 1, max))
# Returns tree if given array of size n can
# represent a BST of n levels.
def canRepresentNLevelBST(arr, n):
root = createNLevelTree(arr, n)
return isBST(root, 0, 2**32)
# Driver code
arr = [512, 330, 78, 11, 8]
n = len(arr)
if (canRepresentNLevelBST(arr, n)):
print("Yes")
else:
print("No")
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to Check given array
// can represent BST or not
using System;
class GFG
{
// structure for Binary Node
public class Node
{
public int key;
public Node right, left;
};
static Node newNode(int num)
{
Node temp = new Node();
temp.key = num;
temp.left = null;
temp.right = null;
return temp;
}
// To create a Tree with n levels. We always
// insert new node to left if it is less than
// previous value.
static Node createNLevelTree(int []arr, int n)
{
Node root = newNode(arr[0]);
Node temp = root;
for (int i = 1; i < n; i++)
{
if (temp.key > arr[i])
{
temp.left = newNode(arr[i]);
temp = temp.left;
}
else
{
temp.right = newNode(arr[i]);
temp = temp.right;
}
}
return root;
}
// Please refer below post for details of this
// function.
// https:// www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
static bool isBST(Node root, int min, int max)
{
if (root == null)
{
return true;
}
if (root.key < min || root.key > max)
{
return false;
}
// Allow only distinct values
return (isBST(root.left, min,
(root.key) - 1) &&
isBST(root.right,
(root.key) + 1, max));
}
// Returns tree if given array of size n can
// represent a BST of n levels.
static bool canRepresentNLevelBST(int []arr, int n)
{
Node root = createNLevelTree(arr, n);
return isBST(root, int.MinValue, int.MaxValue);
}
// Driver code
public static void Main(String[] args)
{
int []arr = {512, 330, 78, 11, 8};
int n = arr.Length;
if (canRepresentNLevelBST(arr, n))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to Check given array
// can represent BST or not
// structure for Binary Node
class Node
{
constructor()
{
this.key = 0;
this.left = null;
this.right = null;
}
};
function newNode(num)
{
var temp = new Node();
temp.key = num;
temp.left = null;
temp.right = null;
return temp;
}
// To create a Tree with n levels. We always
// insert new node to left if it is less than
// previous value.
function createNLevelTree(arr, n)
{
var root = newNode(arr[0]);
var temp = root;
for(var i = 1; i < n; i++)
{
if (temp.key > arr[i])
{
temp.left = newNode(arr[i]);
temp = temp.left;
}
else
{
temp.right = newNode(arr[i]);
temp = temp.right;
}
}
return root;
}
// Please refer below post for details of this
// function.
/*
https:// www.geeksforgeeks.org/a-program-to-
check-if-a-binary-tree-is-bst-or-not/
*/
function isBST(root, min, max)
{
if (root == null)
{
return true;
}
if (root.key < min || root.key > max)
{
return false;
}
// Allow only distinct values
return (isBST(root.left, min,
(root.key) - 1) &&
isBST(root.right,
(root.key) + 1, max));
}
// Returns tree if given array of size n can
// represent a BST of n levels.
function canRepresentNLevelBST(arr, n)
{
var root = createNLevelTree(arr, n);
return isBST(root, -1000000000, 1000000000);
}
// Driver code
var arr = [512, 330, 78, 11, 8];
var n = arr.length;
if (canRepresentNLevelBST(arr, n))
{
document.write("Yes");
}
else
{
document.write("No");
}
</script>
Producción:
Yes
Método 2 (basado en array)
1. Tome dos variables max = INT_MAX para marcar el límite máximo para el subárbol izquierdo y min = INT_MIN para marcar el límite mínimo para el subárbol derecho.
2. Bucle de arr[1] a arr[n-1]
3. para cada elemento verifique
a. Si ( arr[i] > arr[i-1] && arr[i] > min && arr[i] < max ), actualice min = arr[i-1]
b. De lo contrario, si ( arr[i] min && arr[i] < max ), actualice max = arr[i]
c. Si ninguna de las dos condiciones anteriores se cumple, entonces el elemento no se insertará en un nuevo nivel, por lo tanto, rompa.
C++
// C++ program to Check given array
// can represent BST or not
#include <bits/stdc++.h>
using namespace std;
// Driver code
int main()
{
int arr[] = { 5123, 3300, 783, 1111, 890 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = INT_MAX;
int min = INT_MIN;
bool flag = true;
for (int i = 1; i < n; i++) {
// This element can be inserted to the right
// of the previous element, only if it is greater
// than the previous element and in the range.
if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
// max remains same, update min
min = arr[i - 1];
}
// This element can be inserted to the left
// of the previous element, only if it is lesser
// than the previous element and in the range.
else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) {
// min remains same, update max
max = arr[i - 1];
}
else {
flag = false;
break;
}
}
if (flag) {
cout << "Yes";
}
else {
// if the loop completed successfully without encountering else condition
cout << "No";
}
return 0;
}
Java
// Java program to Check given array
// can represent BST or not
class Solution
{
// Driver code
public static void main(String args[])
{
int arr[] = { 5123, 3300, 783, 1111, 890 };
int n = arr.length;
int max = Integer.MAX_VALUE;
int min = Integer.MIN_VALUE;
boolean flag = true;
for (int i = 1; i < n; i++) {
// This element can be inserted to the right
// of the previous element, only if it is greater
// than the previous element and in the range.
if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
// max remains same, update min
min = arr[i - 1];
}
// This element can be inserted to the left
// of the previous element, only if it is lesser
// than the previous element and in the range.
else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) {
// min remains same, update max
max = arr[i - 1];
}
else {
flag = false;
break;
}
}
if (flag) {
System.out.println("Yes");
}
else {
// if the loop completed successfully without encountering else condition
System.out.println("No");
}
}
}
//contributed by Arnab Kundu
Python3
# Python3 program to Check given array
# can represent BST or not
# Driver Code
if __name__ == '__main__':
arr = [5123, 3300, 783, 1111, 890]
n = len(arr)
max = 2147483647 # INT_MAX
min = -2147483648 # INT_MIN
flag = True
for i in range(1,n):
# This element can be inserted to the
# right of the previous element, only
# if it is greater than the previous
# element and in the range.
if (arr[i] > arr[i - 1] and
arr[i] > min and arr[i] < max):
# max remains same, update min
min = arr[i - 1]
# This element can be inserted to the
# left of the previous element, only
# if it is lesser than the previous
# element and in the range.
elif (arr[i] < arr[i - 1] and
arr[i] > min and arr[i] < max):
# min remains same, update max
max = arr[i - 1]
else :
flag = False
break
if (flag):
print("Yes")
else:
# if the loop completed successfully
# without encountering else condition
print("No")
# This code is contributed
# by SHUBHAMSINGH10
C#
using System;
// C# program to Check given array
// can represent BST or not
public class Solution
{
// Driver code
public static void Main(string[] args)
{
int[] arr = new int[] {5123, 3300, 783, 1111, 890};
int n = arr.Length;
int max = int.MaxValue;
int min = int.MinValue;
bool flag = true;
for (int i = 1; i < n; i++)
{
// This element can be inserted to the right
// of the previous element, only if it is greater
// than the previous element and in the range.
if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max)
{
// max remains same, update min
min = arr[i - 1];
}
// This element can be inserted to the left
// of the previous element, only if it is lesser
// than the previous element and in the range.
else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max)
{
// min remains same, update max
max = arr[i - 1];
}
else
{
flag = false;
break;
}
}
if (flag)
{
Console.WriteLine("Yes");
}
else
{
// if the loop completed successfully without encountering else condition
Console.WriteLine("No");
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to Check given array
// can represent BST or not
let arr = [ 5123, 3300, 783, 1111, 890 ];
let n = arr.length;
let max = Number.MAX_VALUE;
let min = Number.MIN_VALUE;
let flag = true;
for (let i = 1; i < n; i++)
{
// This element can be inserted to the right
// of the previous element, only if it is greater
// than the previous element and in the range.
if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max)
{
// max remains same, update min
min = arr[i - 1];
}
// This element can be inserted to the left
// of the previous element, only if it is lesser
// than the previous element and in the range.
else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max)
{
// min remains same, update max
max = arr[i - 1];
}
else {
flag = false;
break;
}
}
if (flag)
{
document.write("Yes");
}
else
{
// if the loop completed successfully without encountering else condition
document.write("No");
}
// This code is contributed by divyesh072019.
</script>
Producción:
Yes
Publicación traducida automáticamente
Artículo escrito por nickhilrawat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA