Dado un árbol binario , la tarea es verificar si el árbol binario dado es un árbol de búsqueda binaria o no. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba «NO» .
Ejemplos:
Aporte:
9 / \ 6 10 / \ \ 4 7 11 / \ \ 3 5 8Salida: SÍ
Explicación: Dado que el subárbol izquierdo de cada Node del árbol consta de Nodes de menor valor y el subárbol derecho de cada Node del árbol consta de Nodes de mayor valor. Por lo tanto, la salida requerida es «SÍ».Aporte:
5 / \ 6 3 / \ \ 4 9 2Salida: NO
Enfoque recursivo: consulte la publicación anterior para resolver este problema utilizando la recursividad.
Complejidad de tiempo: O(N) donde N es el recuento de Nodes en el árbol binario.
Espacio Auxiliar: O(N)
Enfoque iterativo: para resolver el problema de forma iterativa, use Stack . Siga los pasos a continuación para resolver el problema:
- Inicialice una pila para almacenar los Nodes junto con su subárbol izquierdo.
- Inicialice una variable, digamos prev , para almacenar el Node visitado anteriormente del árbol binario.
- Atraviese el árbol e inserte el Node raíz y el subárbol izquierdo de cada Node en la pila y verifique si el valor de los datos del Node anterior es mayor o igual que el valor de los datos del Node visitado actual o no. Si es cierto, escriba “NO” .
- De lo contrario, escriba “SI” .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a tree node
struct TreeNode {
// Stores data value of a node
int data;
// Stores left subtree
// of a tree node
TreeNode* left;
// Stores right subtree
// of a tree node
TreeNode* right;
// Initialization of
// a tree node
TreeNode(int val)
{
// Update data
data = val;
// Update left and right
left = right = NULL;
}
};
// Function to check if a binary tree
// is binary search tree or not
bool checkTreeIsBST(TreeNode *root)
{
// Stores root node and left
// subtree of each node
stack<TreeNode* > Stack;
// Stores previous visited node
TreeNode* prev = NULL;
// Traverse the binary tree
while (!Stack.empty() ||
root != NULL) {
// Traverse left subtree
while (root != NULL) {
// Insert root into Stack
Stack.push(root);
// Update root
root = root->left;
}
// Stores top element of Stack
root = Stack.top();
// Remove the top element of Stack
Stack.pop();
// If data value of root node less
// than data value of left subtree
if(prev != NULL &&
root->data <= prev->data) {
return false;
}
// Update prev
prev = root;
// Traverse right subtree
// of the tree
root = root->right;
}
return true;
}
// Driver Code
int main()
{
/*
9
/ \
6 10
/ \ \
4 7 11
/ \ \
3 5 8
*/
// Initialize binary tree
TreeNode *root = new TreeNode(9);
root->left = new TreeNode(6);
root->right = new TreeNode(10);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(7);
root->right->right = new TreeNode(11);
root->left->left->left = new TreeNode(3);
root->left->left->right = new TreeNode(5);
root->left->right->right = new TreeNode(8);
if (checkTreeIsBST(root)) {
cout<<"YES";
}
else {
cout<<"NO";
}
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Structure of a tree node
static class TreeNode {
// Stores data value of a node
int data;
// Stores left subtree
// of a tree node
TreeNode left;
// Stores right subtree
// of a tree node
TreeNode right;
// Initialization of
// a tree node
TreeNode(int val)
{
// Update data
data = val;
// Update left and right
left = right = null;
}
};
// Function to check if a binary tree
// is binary search tree or not
static boolean checkTreeIsBST(TreeNode root)
{
// Stores root node and left
// subtree of each node
Stack<TreeNode > Stack = new Stack<TreeNode >();
// Stores previous visited node
TreeNode prev = null;
// Traverse the binary tree
while (!Stack.isEmpty() ||
root != null) {
// Traverse left subtree
while (root != null) {
// Insert root into Stack
Stack.add(root);
// Update root
root = root.left;
}
// Stores top element of Stack
root = Stack.peek();
// Remove the top element of Stack
Stack.pop();
// If data value of root node less
// than data value of left subtree
if(prev != null &&
root.data <= prev.data) {
return false;
}
// Update prev
prev = root;
// Traverse right subtree
// of the tree
root = root.right;
}
return true;
}
// Driver Code
public static void main(String[] args)
{
/*
9
/ \
6 10
/ \ \
4 7 11
/ \ \
3 5 8
*/
// Initialize binary tree
TreeNode root = new TreeNode(9);
root.left = new TreeNode(6);
root.right = new TreeNode(10);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(7);
root.right.right = new TreeNode(11);
root.left.left.left = new TreeNode(3);
root.left.left.right = new TreeNode(5);
root.left.right.right = new TreeNode(8);
if (checkTreeIsBST(root)) {
System.out.print("YES");
}
else {
System.out.print("NO");
}
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement
# the above approach
# Structure of a tree node
class TreeNode:
def __init__(self, data: int) -> None:
# Stores data value of a node
self.data = data
# Stores left subtree
# of a tree node
self.left = None
# Stores right subtree
# of a tree node
self.right = None
# Function to check if a binary tree
# is binary search tree or not
def checkTreeIsBST(root: TreeNode) -> bool:
# Stores root node and left
# subtree of each node
Stack = []
# Stores previous visited node
prev = None
# Traverse the binary tree
while (Stack or root):
# Traverse left subtree
while root:
# Insert root into Stack
Stack.append(root)
# Update root
root = root.left
# Stores top element of Stack
# Remove the top element of Stack
root = Stack.pop()
# If data value of root node less
# than data value of left subtree
if (prev and root.data <= prev.data):
return False
# Update prev
prev = root
# Traverse right subtree
# of the tree
root = root.right
return True
# Driver Code
if __name__ == "__main__":
'''
9
/ \
6 10
/ \ \
4 7 11
/ \ \
3 5 8
'''
# Initialize binary tree
root = TreeNode(9)
root.left = TreeNode(6)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(7)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(5)
root.left.right.right = TreeNode(8)
if checkTreeIsBST(root):
print("YES")
else:
print("NO")
# This code is contributed by sanjeev2552
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Structure of a tree node
class TreeNode
{
// Stores data value of a node
public int data;
// Stores left subtree
// of a tree node
public TreeNode left;
// Stores right subtree
// of a tree node
public TreeNode right;
// Initialization of
// a tree node
public TreeNode(int val)
{
// Update data
data = val;
// Update left and right
left = right = null;
}
};
// Function to check if a binary tree
// is binary search tree or not
static bool checkTreeIsBST(TreeNode root)
{
// Stores root node and left
// subtree of each node
Stack<TreeNode > Stack = new Stack<TreeNode >();
// Stores previous visited node
TreeNode prev = null;
// Traverse the binary tree
while (Stack.Count!=0 ||
root != null)
{
// Traverse left subtree
while (root != null)
{
// Insert root into Stack
Stack.Push(root);
// Update root
root = root.left;
}
// Stores top element of Stack
root = Stack.Peek();
// Remove the top element of Stack
Stack.Pop();
// If data value of root node less
// than data value of left subtree
if(prev != null &&
root.data <= prev.data)
{
return false;
}
// Update prev
prev = root;
// Traverse right subtree
// of the tree
root = root.right;
}
return true;
}
// Driver Code
public static void Main(String[] args)
{
/*
9
/ \
6 10
/ \ \
4 7 11
/ \ \
3 5 8
*/
// Initialize binary tree
TreeNode root = new TreeNode(9);
root.left = new TreeNode(6);
root.right = new TreeNode(10);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(7);
root.right.right = new TreeNode(11);
root.left.left.left = new TreeNode(3);
root.left.left.right = new TreeNode(5);
root.left.right.right = new TreeNode(8);
if (checkTreeIsBST(root))
{
Console.Write("YES");
}
else
{
Console.Write("NO");
}
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// Structure of a tree node
class TreeNode
{
constructor(val)
{
// Stores left subtree
// of a tree node
this.left = null;
// Stores right subtree
// of a tree node
this.right = null;
// Stores data value of a node
this.data = val;
}
}
// Function to check if a binary tree
// is binary search tree or not
function checkTreeIsBST(root)
{
// Stores root node and left
// subtree of each node
let Stack = [];
// Stores previous visited node
let prev = null;
// Traverse the binary tree
while (Stack.length > 0 || root != null)
{
// Traverse left subtree
while (root != null)
{
// Insert root into Stack
Stack.push(root);
// Update root
root = root.left;
}
// Stores top element of Stack
root = Stack[Stack.length - 1];
// Remove the top element of Stack
Stack.pop();
// If data value of root node less
// than data value of left subtree
if (prev != null &&
root.data <= prev.data)
{
return false;
}
// Update prev
prev = root;
// Traverse right subtree
// of the tree
root = root.right;
}
return true;
}
// Driver code
/*
9
/ \
6 10
/ \ \
4 7 11
/ \ \
3 5 8
*/
// Initialize binary tree
let root = new TreeNode(9);
root.left = new TreeNode(6);
root.right = new TreeNode(10);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(7);
root.right.right = new TreeNode(11);
root.left.left.left = new TreeNode(3);
root.left.left.right = new TreeNode(5);
root.left.right.right = new TreeNode(8);
if (checkTreeIsBST(root))
{
document.write("YES");
}
else
{
document.write("NO");
}
// This code is contributed by divyeshrabadiya07
</script>
Producción:
YES
Complejidad de tiempo: O(N), donde N es el conteo de Nodes en el árbol binario
Espacio auxiliar: O(N)