Dado un árbol binario, la tarea es verificar si el árbol binario dado es un árbol de búsqueda binario o no.
Un árbol de búsqueda binario (BST) es una estructura de datos de árbol binario basada en Nodes que tiene las siguientes propiedades.
- El subárbol izquierdo de un Node contiene solo Nodes con claves menores que la clave del Node.
- El subárbol derecho de un Node contiene solo Nodes con claves mayores que la clave del Node.
- Los subárboles izquierdo y derecho también deben ser árboles de búsqueda binarios.
De las propiedades anteriores se deduce naturalmente que:
- Cada Node (elemento en el árbol) tiene una clave distinta.
Ya hemos discutido diferentes enfoques para resolver este problema en el artículo anterior .
En este artículo, discutiremos un enfoque simple pero eficiente para resolver el problema anterior.
La idea es utilizar el recorrido Inorder y realizar un seguimiento del valor del Node visitado anteriormente. Dado que el recorrido en orden de un BST genera una array ordenada como salida, por lo tanto, el elemento anterior siempre debe ser menor o igual que el elemento actual.
Mientras realizamos el recorrido en orden, podemos realizar un seguimiento del valor del Node visitado anteriormente y si el valor del Node visitado actualmente es menor que el valor anterior, entonces el árbol no es BST.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if a given tree is BST.
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
struct Node {
int data;
struct Node *left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
// Utility function to check if Binary Tree is BST
bool isBSTUtil(struct Node* root, int& prev)
{
// traverse the tree in inorder fashion and
// keep track of prev node
if (root) {
if (!isBSTUtil(root->left, prev))
return false;
// Allows only distinct valued nodes
if (root->data <= prev)
return false;
// Initialize prev to current
prev = root->data;
return isBSTUtil(root->right, prev);
}
return true;
}
// Function to check if Binary Tree is BST
bool isBST(Node* root)
{
int prev = INT_MIN;
return isBSTUtil(root, prev);
}
/* Driver code*/
int main()
{
struct Node* root = new Node(5);
root->left = new Node(2);
root->right = new Node(15);
root->left->left = new Node(1);
root->left->right = new Node(4);
if (isBST(root))
cout << "Is BST";
else
cout << "Not a BST";
return 0;
}
Java
// Java program to check if a given tree is BST.
class GFG {
static int prev = Integer.MIN_VALUE;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
static class Node {
int data;
Node left, right;
Node(int data)
{
this.data = data;
left = right = null;
}
};
// Utility function to check if Binary Tree is BST
static boolean isBSTUtil(Node root)
{
// traverse the tree in inorder fashion and
// keep track of prev node
if (root != null) {
if (!isBSTUtil(root.left))
return false;
// Allows only distinct valued nodes
if (root.data <= prev)
return false;
// Initialize prev to current
prev = root.data;
return isBSTUtil(root.right);
}
return true;
}
// Function to check if Binary Tree is BST
static boolean isBST(Node root)
{
return isBSTUtil(root);
}
/* Driver code*/
public static void main(String[] args)
{
Node root = new Node(5);
root.left = new Node(2);
root.right = new Node(15);
root.left.left = new Node(1);
root.left.right = new Node(4);
if (isBST(root))
System.out.print("Is BST");
else
System.out.print("Not a BST");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to check if a given tree is BST.
import math
prev = -math.inf
class Node:
"""
Creates a Binary tree node that has data,
a pointer to it's left and right child
"""
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def checkBST(root):
"""
Function to check if Binary Tree is
a Binary Search Tree
:param root: current root node
:return: Boolean value
"""
# traverse the tree in inorder
# fashion and update the prev node
global prev
if root:
if not checkBST(root.left):
return False
# Handles same valued nodes
if root.data < prev:
return False
# Set value of prev to current node
prev = root.data
return checkBST(root.right)
return True
# Driver Code
def main():
root = Node(1)
root.left = Node(2)
root.right = Node(15)
root.left.left = Node(1)
root.left.right = Node(4)
if checkBST(root):
print("Is BST")
else:
print("Not a BST")
if __name__ == '__main__':
main()
# This code is contributed by priyankapunjabi94
C#
// C# program to check if a given tree is BST.
using System;
class GFG {
/* A binary tree node has data, pointer to
left child and a pointer to right child */
class Node {
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
};
// Utility function to check if Binary Tree is BST
static bool isBSTUtil(Node root, int prev)
{
// traverse the tree in inorder fashion and
// keep track of prev node
if (root != null) {
if (!isBSTUtil(root.left, prev))
return false;
// Allows only distinct valued nodes
if (root.data <= prev)
return false;
// Initialize prev to current
prev = root.data;
return isBSTUtil(root.right, prev);
}
return true;
}
// Function to check if Binary Tree is BST
static bool isBST(Node root)
{
int prev = int.MinValue;
return isBSTUtil(root, prev);
}
/* Driver code*/
public static void Main(String[] args)
{
Node root = new Node(5);
root.left = new Node(2);
root.right = new Node(15);
root.left.left = new Node(1);
root.left.right = new Node(4);
if (isBST(root))
Console.Write("Is BST");
else
Console.Write("Not a BST");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to check if a given tree is BST.
/* A binary tree node has data, pointer to
left child and a pointer to right child */
class Node {
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// Utility function to check if Binary Tree is BST
function isBSTUtil(root, prev)
{
// traverse the tree in inorder fashion and
// keep track of prev node
if (root != null) {
if (!isBSTUtil(root.left, prev))
return false;
// Allows only distinct valued nodes
if (root.data <= prev)
return false;
// Initialize prev to current
prev = root.data;
return isBSTUtil(root.right, prev);
}
return true;
}
// Function to check if Binary Tree is BST
function isBST(root)
{
var prev = -1000000000;
return isBSTUtil(root, prev);
}
/* Driver code*/
var root = new Node(5);
root.left = new Node(2);
root.right = new Node(15);
root.left.left = new Node(1);
root.left.right = new Node(4);
if (isBST(root))
document.write("Is BST");
else
document.write("Not a BST");
</script>
Producción
Is BST
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harsh.agarwal0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA