Dada una array de tamaño n . El problema es verificar si la array dada puede representar el recorrido de orden de niveles de un árbol de búsqueda binaria o no.
Ejemplos:
Input : arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10}
Output : Yes
For the given arr[] the Binary Search Tree is:
7
/ \
4 12
/ \ /
3 6 8
/ / \
1 5 10
Input : arr[] = {11, 6, 13, 5, 12, 10}
Output : No
The given arr[] do not represent the level
order traversal of a BST.
La idea es utilizar una estructura de datos de cola. Cada elemento de la cola tiene una estructura, digamos NodeDetails , que almacena detalles de un Node de árbol. Los detalles son los datos del Node y dos variables min y max donde min almacena el límite inferior para los valores del Node que pueden ser parte del subárbol izquierdo y max almacena el límite superior para los valores del Node que pueden ser parte del subárbol derecho para el Node especificado en la variable de estructura NodeDetails . Para el primer valor de array arr[0], cree una estructura NodeDetails que tenga arr[0] como datos del Node y min = INT_MIN y max= INT_MAX. Agregue esta variable de estructura a la cola. Este Node será la raíz del árbol. Vaya al segundo elemento en arr[] y luego realice los siguientes pasos:
- Pop NodeDetails de la cola en temp .
- Compruebe si el elemento de array actual puede ser un elemento secundario izquierdo del Node en temp con la ayuda de los valores min y temp.data . Si es posible, cree una nueva estructura NodeDetails para este nuevo valor de elemento de array con sus valores ‘min’ y ‘max’ apropiados y empújelo a la cola, y muévase al siguiente elemento en arr[].
- Compruebe si el elemento de array actual puede ser un hijo derecho del Node en temp con la ayuda de los valores max y temp.data . Si es posible, cree una nueva estructura NodeDetails para este nuevo valor de elemento de array con sus valores ‘min’ y ‘max’ apropiados y empújelo a la cola, y muévase al siguiente elemento en arr[].
- Repita los pasos 1, 2 y 3 hasta que no haya más elementos en arr[] o no haya más elementos en la cola.
Finalmente, si se han recorrido todos los elementos de la array, entonces la array representa el recorrido de orden de nivel de un BST; de lo contrario, NO.
C++
// C++ implementation to check if the given array
// can represent Level Order Traversal of Binary
// Search Tree
#include <bits/stdc++.h>
using namespace std;
// to store details of a node like
// node's data, 'min' and 'max' to obtain the
// range of values where node's left and
// right child's should lie
struct NodeDetails
{
int data;
int min, max;
};
// function to check if the given array
// can represent Level Order Traversal
// of Binary Search Tree
bool levelOrderIsOfBST(int arr[], int n)
{
// if tree is empty
if (n == 0)
return true;
// queue to store NodeDetails
queue<NodeDetails> q;
// index variable to access array elements
int i=0;
// node details for the
// root of the BST
NodeDetails newNode;
newNode.data = arr[i++];
newNode.min = INT_MIN;
newNode.max = INT_MAX;
q.push(newNode);
// until there are no more elements
// in arr[] or queue is not empty
while (i != n && !q.empty())
{
// extracting NodeDetails of a
// node from the queue
NodeDetails temp = q.front();
q.pop();
// check whether there are more elements
// in the arr[] and arr[i] can be left child
// of 'temp.data' or not
if (i < n && (arr[i] < temp.data &&
arr[i] > temp.min))
{
// Create NodeDetails for newNode
/// and add it to the queue
newNode.data = arr[i++];
newNode.min = temp.min;
newNode.max = temp.data;
q.push(newNode);
}
// check whether there are more elements
// in the arr[] and arr[i] can be right child
// of 'temp.data' or not
if (i < n && (arr[i] > temp.data &&
arr[i] < temp.max))
{
// Create NodeDetails for newNode
/// and add it to the queue
newNode.data = arr[i++];
newNode.min = temp.data;
newNode.max = temp.max;
q.push(newNode);
}
}
// given array represents level
// order traversal of BST
if (i == n)
return true;
// given array do not represent
// level order traversal of BST
return false;
}
// Driver program to test above
int main()
{
int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};
int n = sizeof(arr) / sizeof(arr[0]);
if (levelOrderIsOfBST(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation to check if the given array
// can represent Level Order Traversal of Binary
// Search Tree
import java.util.*;
class Solution
{
// to store details of a node like
// node's data, 'min' and 'max' to obtain the
// range of values where node's left and
// right child's should lie
static class NodeDetails
{
int data;
int min, max;
};
// function to check if the given array
// can represent Level Order Traversal
// of Binary Search Tree
static boolean levelOrderIsOfBST(int arr[], int n)
{
// if tree is empty
if (n == 0)
return true;
// queue to store NodeDetails
Queue<NodeDetails> q = new LinkedList<NodeDetails>();
// index variable to access array elements
int i = 0;
// node details for the
// root of the BST
NodeDetails newNode=new NodeDetails();
newNode.data = arr[i++];
newNode.min = Integer.MIN_VALUE;
newNode.max = Integer.MAX_VALUE;
q.add(newNode);
// until there are no more elements
// in arr[] or queue is not empty
while (i != n && q.size() > 0)
{
// extracting NodeDetails of a
// node from the queue
NodeDetails temp = q.peek();
q.remove();
newNode = new NodeDetails();
// check whether there are more elements
// in the arr[] and arr[i] can be left child
// of 'temp.data' or not
if (i < n && (arr[i] < (int)temp.data &&
arr[i] > (int)temp.min))
{
// Create NodeDetails for newNode
/// and add it to the queue
newNode.data = arr[i++];
newNode.min = temp.min;
newNode.max = temp.data;
q.add(newNode);
}
newNode=new NodeDetails();
// check whether there are more elements
// in the arr[] and arr[i] can be right child
// of 'temp.data' or not
if (i < n && (arr[i] > (int)temp.data &&
arr[i] < (int)temp.max))
{
// Create NodeDetails for newNode
/// and add it to the queue
newNode.data = arr[i++];
newNode.min = temp.data;
newNode.max = temp.max;
q.add(newNode);
}
}
// given array represents level
// order traversal of BST
if (i == n)
return true;
// given array do not represent
// level order traversal of BST
return false;
}
// Driver code
public static void main(String args[])
{
int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};
int n = arr.length;
if (levelOrderIsOfBST(arr, n))
System.out.print( "Yes");
else
System.out.print( "No");
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation to check if the
# given array can represent Level Order
# Traversal of Binary Search Tree
INT_MIN, INT_MAX = float('-inf'), float('inf')
# To store details of a node like node's
# data, 'min' and 'max' to obtain the
# range of values where node's left
# and right child's should lie
class NodeDetails:
def __init__(self, data, min, max):
self.data = data
self.min = min
self.max = max
# function to check if the given array
# can represent Level Order Traversal
# of Binary Search Tree
def levelOrderIsOfBST(arr, n):
# if tree is empty
if n == 0:
return True
# queue to store NodeDetails
q = []
# index variable to access array elements
i = 0
# node details for the root of the BST
newNode = NodeDetails(arr[i], INT_MIN, INT_MAX)
i += 1
q.append(newNode)
# until there are no more elements
# in arr[] or queue is not empty
while i != n and len(q) != 0:
# extracting NodeDetails of a
# node from the queue
temp = q.pop(0)
# check whether there are more elements
# in the arr[] and arr[i] can be left
# child of 'temp.data' or not
if i < n and (arr[i] < temp.data and
arr[i] > temp.min):
# Create NodeDetails for newNode
#/ and add it to the queue
newNode = NodeDetails(arr[i], temp.min, temp.data)
i += 1
q.append(newNode)
# check whether there are more elements
# in the arr[] and arr[i] can be right
# child of 'temp.data' or not
if i < n and (arr[i] > temp.data and
arr[i] < temp.max):
# Create NodeDetails for newNode
#/ and add it to the queue
newNode = NodeDetails(arr[i], temp.data, temp.max)
i += 1
q.append(newNode)
# given array represents level
# order traversal of BST
if i == n:
return True
# given array do not represent
# level order traversal of BST
return False
# Driver code
if __name__ == "__main__":
arr = [7, 4, 12, 3, 6, 8, 1, 5, 10]
n = len(arr)
if levelOrderIsOfBST(arr, n):
print("Yes")
else:
print("No")
# This code is contributed by Rituraj Jain
C#
// C# implementation to check if the given array
// can represent Level Order Traversal of Binary
// Search Tree
using System;
using System.Collections.Generic;
class GFG
{
// to store details of a node like
// node's data, 'min' and 'max' to obtain the
// range of values where node's left and
// right child's should lie
public class NodeDetails
{
public int data;
public int min, max;
};
// function to check if the given array
// can represent Level Order Traversal
// of Binary Search Tree
static Boolean levelOrderIsOfBST(int []arr, int n)
{
// if tree is empty
if (n == 0)
return true;
// queue to store NodeDetails
Queue<NodeDetails> q = new Queue<NodeDetails>();
// index variable to access array elements
int i = 0;
// node details for the
// root of the BST
NodeDetails newNode=new NodeDetails();
newNode.data = arr[i++];
newNode.min = int.MinValue;
newNode.max = int.MaxValue;
q.Enqueue(newNode);
// until there are no more elements
// in arr[] or queue is not empty
while (i != n && q.Count > 0)
{
// extracting NodeDetails of a
// node from the queue
NodeDetails temp = q.Peek();
q.Dequeue();
newNode = new NodeDetails();
// check whether there are more elements
// in the arr[] and arr[i] can be left child
// of 'temp.data' or not
if (i < n && (arr[i] < (int)temp.data &&
arr[i] > (int)temp.min))
{
// Create NodeDetails for newNode
/// and add it to the queue
newNode.data = arr[i++];
newNode.min = temp.min;
newNode.max = temp.data;
q.Enqueue(newNode);
}
newNode=new NodeDetails();
// check whether there are more elements
// in the arr[] and arr[i] can be right child
// of 'temp.data' or not
if (i < n && (arr[i] > (int)temp.data &&
arr[i] < (int)temp.max))
{
// Create NodeDetails for newNode
/// and add it to the queue
newNode.data = arr[i++];
newNode.min = temp.data;
newNode.max = temp.max;
q.Enqueue(newNode);
}
}
// given array represents level
// order traversal of BST
if (i == n)
return true;
// given array do not represent
// level order traversal of BST
return false;
}
// Driver code
public static void Main(String []args)
{
int []arr = {7, 4, 12, 3, 6, 8, 1, 5, 10};
int n = arr.Length;
if (levelOrderIsOfBST(arr, n))
Console.Write( "Yes");
else
Console.Write( "No");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to check if
// the given array can represent Level
// Order Traversal of Binary Search Tree
// To store details of a node like node's
// data, 'min' and 'max' to obtain the
// range of values where node's left and
// right child's should lie
class NodeDetails
{
constructor()
{
this.min;
this.max;
this.data;
}
}
// Function to check if the given array
// can represent Level Order Traversal
// of Binary Search Tree
function levelOrderIsOfBST(arr, n)
{
// If tree is empty
if (n == 0)
return true;
// Queue to store NodeDetails
let q = [];
// Index variable to access array elements
let i = 0;
// Node details for the
// root of the BST
let newNode = new NodeDetails();
newNode.data = arr[i++];
newNode.min = Number.MIN_VALUE;
newNode.max = Number.MAX_VALUE;
q.push(newNode);
// Until there are no more elements
// in arr[] or queue is not empty
while (i != n && q.length > 0)
{
// Extracting NodeDetails of a
// node from the queue
let temp = q[0];
q.shift();
newNode = new NodeDetails();
// Check whether there are more elements
// in the arr[] and arr[i] can be left child
// of 'temp.data' or not
if (i < n && (arr[i] < temp.data &&
arr[i] > temp.min))
{
// Create NodeDetails for newNode
// and add it to the queue
newNode.data = arr[i++];
newNode.min = temp.min;
newNode.max = temp.data;
q.push(newNode);
}
newNode = new NodeDetails();
// Check whether there are more elements
// in the arr[] and arr[i] can be right child
// of 'temp.data' or not
if (i < n && (arr[i] > temp.data &&
arr[i] < temp.max))
{
// Create NodeDetails for newNode
// and add it to the queue
newNode.data = arr[i++];
newNode.min = temp.data;
newNode.max = temp.max;
q.push(newNode);
}
}
// Given array represents level
// order traversal of BST
if (i == n)
return true;
// Given array do not represent
// level order traversal of BST
return false;
}
// Driver code
let arr = [ 7, 4, 12, 3, 6, 8, 1, 5, 10 ];
let n = arr.length;
if (levelOrderIsOfBST(arr, n))
document.write("Yes");
else
document.write("No");
// This code is contributed by vaibhavrabadiya3
</script>
Producción
Yes
Complejidad de tiempo: O(n)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA