¿Cómo se valida un árbol de búsqueda binario?

Leí aquí un ejercicio de entrevistas conocido como validación de un árbol de búsqueda binario.

¿Cómo funciona esto exactamente? ¿Qué se estaría buscando para validar un árbol de búsqueda binario? Escribí un árbol de búsqueda básico, pero nunca escuché acerca de este concepto.

En realidad ese es el error que todos hacen en una entrevista.

Leftchild se debe comparar con (minLimitof node, node.value)

Se debe comparar a Rightchild con (node.value, MaxLimit of node)

IsValidBST(root,-infinity,infinity); bool IsValidBST(BinaryNode node, int MIN, int MAX) { if(node == null) return true; if(node.element > MIN && node.element < MAX && IsValidBST(node.left,MIN,node.element) && IsValidBST(node.right,node.element,MAX)) return true; else return false; } 

Otra solución (si el espacio no es una restricción): realice un recorrido inorden del árbol y almacene los valores del nodo en una matriz. Si la matriz está ordenada, es una BST válida; de lo contrario, no.

“Validar” un árbol de búsqueda binario significa que usted verifica que sí tiene todos los elementos más pequeños a la izquierda y los grandes a la derecha. Básicamente, es un control para ver si un árbol binario es un árbol de búsqueda binario.

La mejor solución que encontré es O (n) y no usa espacio extra. Es similar al recorrido intermedio, pero en lugar de almacenarlo en una matriz y luego verificar si está ordenado podemos tomar una variable estática y verificar, mientras ordenamos, si la matriz está ordenada.

 static struct node *prev = NULL; bool isBST(struct node* root) { // traverse the tree in inorder fashion and keep track of prev node if (root) { if (!isBST(root->left)) return false; // Allows only distinct valued nodes if (prev != NULL && root->data < = prev->data) return false; prev = root; return isBST(root->right); } return true; } 

Solución iterativa usando inorder transversal.

 bool is_bst(Node *root) { if (!root) return true; std::stack stack; bool started = false; Node *node = root; int prev_val; while(true) { if (node) { stack.push(node); node = node->left(); continue; } if (stack.empty()) break; node = stack.top(); stack.pop(); /* beginning of bst check */ if(!started) { prev_val = node->val(); started = true; } else { if (prev_val > node->val()) return false; prev_val = node->val(); } /* end of bst check */ node = node->right(); } return true; } 

Aquí está mi solución en Clojure:

 (defstruct BST :val :left :right) (defn in-order [bst] (when-let [{:keys [val, left, right]} bst] (lazy-seq (concat (in-order left) (list val) (in-order right))))) (defn is-strictly-sorted? [col] (every? (fn [[ab]] (< ab)) (partition 2 1 col))) (defn is-valid-BST [bst] (is-strictly-sorted? (in-order bst))) 

Como el recorrido en orden de una BST es una secuencia sin disminución, podríamos usar esta propiedad para juzgar si un árbol binario es BST o no. Usando Morris transversal y manteniendo el prenodo, podríamos obtener una solución en O (n) tiempo y O (1) complejidad de espacio . Aquí está mi código

 public boolean isValidBST(TreeNode root) { TreeNode pre = null, cur = root, tmp; while(cur != null) { if(cur.left == null) { if(pre != null && pre.val >= cur.val) return false; pre = cur; cur = cur.right; } else { tmp = cur.left; while(tmp.right != null && tmp.right != cur) tmp = tmp.right; if(tmp.right == null) { // left child has not been visited tmp.right = cur; cur = cur.left; } else { // left child has been visited already tmp.right = null; if(pre != null && pre.val >= cur.val) return false; pre = cur; cur = cur.right; } } } return true; } 

Aquí está mi respuesta en Python, tiene todos los casos de la esquina abordados y bien probados en el sitio web de hackerrank

 """ Node is defined as class node: def __init__(self, data): self.data = data self.left = None self.right = None """ def checkBST(root): return checkLeftSubTree(root, root.left) and checkRightSubTree(root, root.right) def checkLeftSubTree(root, subTree): if not subTree: return True else: return root.data > subTree.data \ and checkLeftSubTree(root, subTree.left) \ and checkLeftSubTree(root, subTree.right) \ and checkLeftSubTree(subTree, subTree.left) \ and checkRightSubTree(subTree, subTree.right) def checkRightSubTree(root, subTree): if not subTree: return True else: return root.data < subTree.data \ and checkRightSubTree(root, subTree.left) \ and checkRightSubTree(root, subTree.right) \ and checkRightSubTree(subTree, subTree.right) \ and checkLeftSubTree(subTree, subTree.left) 
 bool BinarySearchTree::validate() { int minVal = -1; int maxVal = -1; return ValidateImpl(root, minVal, maxVal); } bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal) { int leftMin = -1; int leftMax = -1; int rightMin = -1; int rightMax = -1; if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value < currRoot->value) { if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false; if (leftMax != currRoot->left->value && currRoot->value < leftMax) return false; } else return false; } else { leftMin = leftMax = currRoot->value; } if (currRoot->right) { if (currRoot->right->value > currRoot->value) { if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false; if (rightMin != currRoot->right->value && currRoot->value > rightMin) return false; } else return false; } else { rightMin = rightMax = currRoot->value; } minVal = leftMin < rightMin ? leftMin : rightMin; maxVal = leftMax > rightMax ? leftMax : rightMax; return true; } 

“Es mejor definir primero un invariante. Aquí lo invariante: cualquier dos elementos secuenciales del BST en el recorrido en orden debe estar en un orden estrictamente creciente de su apariencia (no puede ser igual, siempre aumenta en orden) transversal). Por lo tanto, la solución puede ser simplemente un recorrido en línea simple con recordar el último nodo visitado y comparar el nodo actual con el último visitado con ‘< ' (o '>‘).

 bool ValidateBST(Node *pCurrentNode, int nMin = INT_MIN, int nMax = INT_MAX) { return ( pCurrentNode == NULL ) || ( ( !pCurrentNode->pLeftNode || ( pCurrentNode->pLeftNode->value < pCurrentNode->value && pCurrentNode->pLeftNode->value < nMax && ValidateBST(pCurrentNode->pLeftNode, nMin, pCurrentNode->value) ) ) && ( !pCurrentNode->pRightNode || ( pCurrentNode->pRightNode->value > pCurrentNode->value && pCurrentNode->pRightNode->value > nMin && ValidateBST(pCurrentNode->pRightNode, pCurrentNode->value, nMax) ) ) ); } 

Recibí esta pregunta en una entrevista telefónica recientemente y luché con ella más de lo que debería. Intentaba hacer un seguimiento de los mínimos y máximos en los nodos de los niños y no podía abarcar mi cerebro en los diferentes casos bajo la presión de una entrevista.

Después de pensarlo mientras me quedaba dormida la noche anterior, me di cuenta de que es tan simple como hacer un seguimiento del último nodo que has visitado durante un recorrido inorden. En Java:

 public > boolean isBst(TreeNode root) { return isBst(root, null); } private > boolean isBst(TreeNode node, TreeNode prev) { if (node == null) return true; if (isBst(node.left, prev) && (prev == null || prev.compareTo(node) < 0 )) return isBst(node.right, node); return false; } 

En Java y permitiendo nodos con el mismo valor en cualquier subárbol:

 public boolean isValid(Node node) { return isValid(node, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isValid(Node node, int minLimit, int maxLimit) { if (node == null) return true; return minLimit < = node.value && node.value <= maxLimit && isValid(node.left, minLimit, node.value) && isValid(node.right, node.value, maxLimit); } 
 // using inorder traverse based Impl bool BinarySearchTree::validate() { int val = -1; return ValidateImpl(root, val); } // inorder traverse based Impl bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) { if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value > currRoot->value) return false; if(!ValidateImpl(currRoot->left, val)) return false; } if (val > currRoot->value) return false; val = currRoot->value; if (currRoot->right) { if (currRoot->right->value < currRoot->value) return false; if(!ValidateImpl(currRoot->right, val)) return false; } return true; } 

Para saber si BT dado es BST para cualquier tipo de datos, debe ir con el siguiente enfoque. 1. llame a la función recursiva hasta el final del nodo hoja utilizando inorder transversal 2. Construya sus valores mínimo y máximo usted mismo.

El elemento de árbol debe tener menos de / mayor que el definido por el operador.

 #define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal) #define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal) template  bool IsValidBST (treeNode &root) { T min, max; return IsValidBST (root, &min, &max); } template  bool IsValidBST (treeNode *root, T *MIN , T *MAX) { T leftMin, leftMax, rightMin, rightMax; bool isValidBST; if (root->leftNode == NULL && root->rightNode == NULL) { *MIN = root->element; *MAX = root->element; return true; } isValidBST = IsValidBST (root->leftNode, &leftMin, &leftMax); if (isValidBST) isValidBST = IsValidBST (root->rightNode, &rightMin, &rightMax); if (isValidBST) { *MIN = MIN (leftMIN, rightMIN); *Max = MAX (rightMax, leftMax); } return isValidBST; } 
 bool isBST(struct node* root) { static struct node *prev = NULL; // traverse the tree in inorder fashion and keep track of prev node if (root) { if (!isBST(root->left)) return false; // Allows only distinct valued nodes if (prev != NULL && root->data < = prev->data) return false; prev = root; return isBST(root->right); } return true; } 

Funciona bien 🙂

La recursividad es fácil pero el enfoque iterativo es mejor, hay una versión iterativa arriba pero es demasiado compleja de lo necesario. Aquí está la mejor solución en c++ que encontrarás en cualquier lugar:

Este algoritmo se ejecuta en tiempo O(N) y necesita espacio O(lgN) .

 struct TreeNode { int value; TreeNode* left; TreeNode* right; }; bool isBST(TreeNode* root) { vector stack; TreeNode* prev = nullptr; while (root || stack.size()) { if (root) { stack.push_back(root); root = root->left; } else { if (prev && stack.back()->value < = prev->value) return false; prev = stack.back(); root = prev->right; stack.pop_back(); } } return true; } 

Escribí una solución para usar Inorder Traversal BST y comprobar si los nodos están aumentando el orden para el espacio O(1) Y el tiempo O(n) . TreeNode predecessor es el nodo anterior. No estoy seguro de que la solución sea correcta o no. Porque el inorder Traversal no puede definir un árbol completo.

 public boolean isValidBST(TreeNode root, TreeNode predecessor) { boolean left = true, right = true; if (root.left != null) { left = isValidBST(root.left, predecessor); } if (!left) return false; if (predecessor.val > root.val) return false; predecessor.val = root.val; if (root.right != null) { right = isValidBST(root.right, predecessor); } if (!right) return false; return true; } 

A continuación está la implementación de Java de la validación de BST, donde viajamos el árbol en orden DFS y devuelve falso si obtenemos cualquier número que sea mayor que el último número.

 static class BSTValidator { private boolean lastNumberInitialized = false; private int lastNumber = -1; boolean isValidBST(TreeNode node) { if (node.left != null && !isValidBST(node.left)) return false; // In-order visiting should never see number less than previous // in valid BST. if (lastNumberInitialized && (lastNumber > node.getData())) return false; if (!lastNumberInitialized) lastNumberInitialized = true; lastNumber = node.getData(); if (node.right != null && !isValidBST(node.right)) return false; return true; } } 

Solución recursiva:

 isBinary(root) { if root == null return true else if( root.left == NULL and root.right == NULL) return true else if(root.left == NULL) if(root.right.element > root.element) rerturn isBInary(root.right) else if (root.left.element < root.element) return isBinary(root.left) else return isBInary(root.left) and isBinary(root.right) } 

Solución iterativa

 private static boolean checkBst(bst node) { Stack s = new Stack(); bst temp; while(node!=null){ s.push(node); node=node.left; } while (!s.isEmpty()){ node = s.pop(); System.out.println(node.val); temp = node; if(node.right!=null){ node = node.right; while(node!=null) { //Checking if the current value is lesser than the previous value and ancestor. if(node.val < temp.val) return false; if(!s.isEmpty()) if(node.val>s.peek().val) return false; s.push(node); if(node!=null) node=node.left; } } } return true; } 

Esto funciona para duplicados.

 // time O(n), space O(logn) // pseudocode is-bst(node, min = int.min, max = int.max): if node == null: return true if node.value < = min || max < node.value: return false return is-bst(node.left, min, node.value) && is-bst(node.right, node.value, max) 

Esto funciona incluso para los valores int.min e int.max usando tipos Nullable .

 // time O(n), space O(logn) // pseudocode is-bst(node, min = null, max = null): if node == null: return true if min != null && node.value < = min return false if max != null && max < node.value: return false return is-bst(node.left, min, node.value) && is-bst(node.right, node.value, max) 

Inspirado por http://www.jiuzhang.com/solutions/validate-binary-search-tree/

Hay dos soluciones generales: transversal y dividir && conquer.

 public class validateBinarySearchTree { public boolean isValidBST(TreeNode root) { return isBSTTraversal(root) && isBSTDivideAndConquer(root); } // Solution 1: Traversal // The inorder sequence of a BST is a sorted ascending list private int lastValue = 0; // the init value of it doesn't matter. private boolean firstNode = true; public boolean isBSTTraversal(TreeNode root) { if (root == null) { return true; } if (!isValidBST(root.left)) { return false; } // firstNode is needed because of if firstNode is Integer.MIN_VALUE, // even if we set lastValue to Integer.MIN_VALUE, it will still return false if (!firstNode && lastValue >= root.val) { return false; } firstNode = false; lastValue = root.val; if (!isValidBST(root.right)) { return false; } return true; } // Solution 2: divide && conquer private class Result { int min; int max; boolean isBST; Result(int min, int max, boolean isBST) { this.min = min; this.max = max; this.isBST = isBST; } } public boolean isBSTDivideAndConquer(TreeNode root) { return isBSTHelper(root).isBST; } public Result isBSTHelper(TreeNode root) { // For leaf node's left or right if (root == null) { // we set min to Integer.MAX_VALUE and max to Integer.MIN_VALUE // because of in the previous level which is the leaf level, // we want to set the min or max to that leaf node's val (in the last return line) return new Result(Integer.MAX_VALUE, Integer.MIN_VALUE, true); } Result left = isBSTHelper(root.left); Result right = isBSTHelper(root.right); if (!left.isBST || !right.isBST) { return new Result(0,0, false); } // For non-leaf node if (root.left != null && left.max >= root.val && root.right != null && right.min < = root.val) { return new Result(0, 0, false); } return new Result(Math.min(left.min, root.val), Math.max(right.max, root.val), true); } } 

Un trazador de líneas

 bool is_bst(Node *root, int from, int to) { return (root == NULL) ? true : root->val >= from && root->val < = to && is_bst(root->left, from, root->val) && is_bst(root->right, root->val, to); } 

Bastante larga línea sin embargo.

Aquí está la solución iterativa sin usar espacio extra.

 Node{ int value; Node right, left } public boolean ValidateBST(Node root){ Node currNode = root; Node prevNode = null; Stack stack = new Stack(); while(true){ if(currNode != null){ stack.push(currNode); currNode = currNode.left; continue; } if(stack.empty()){ return; } currNode = stack.pop(); if(prevNode != null){ if(currNode.value < prevNode.value){ return false; } } prevNode = currNode; currNode = currNode.right; } } 
  private void validateBinarySearchTree(Node node) { if (node == null) return; Node left = node.getLeft(); if (left != null) { if (left.getData() < node.getData()) { validateBinarySearchTree(left); } else { throw new IllegalStateException("Not a valid Binary Search tree"); } } Node right = node.getRight(); if (right != null) { if (right.getData() > node.getData()) { validateBinarySearchTree(right); } else { throw new IllegalStateException("Not a valid Binary Search tree"); } } } 
 boolean isBST(Node root) { if (root == null) { return true; } return (isBST(root.left) && (isBST(root.right) && (root.left == null || root.left.data < = root.data) && (root.right == null || root.right.data > root.data)); } 

Aquí está mi solución recursiva escrita en JavaScript

 function isBST(tree) { if (tree === null) return true; if (tree.left != undefined && tree.left.value > tree.value) { return false; } if (tree.right != undefined && tree.right.value < = tree.value) { return false; } return isBST(tree.left) && isBST(tree.right); }