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>
YES
Complejidad de tiempo: O(N), donde N es el conteo de Nodes en el árbol binario
Espacio auxiliar: O(N)