Como você valida uma tree de busca binária?

Eu li aqui um exercício de entrevistas conhecido como validando uma tree de busca binária.

Como, exatamente, isso funciona? O que alguém estaria procurando na validação de uma tree de busca binária? Eu escrevi uma tree de busca básica, mas nunca ouvi falar desse conceito.

Na verdade, esse é o erro que todos cometem em uma entrevista.

O Leftchild deve ser verificado em relação a (minLimitof node, node.value)

O Rightchild deve ser verificado em relação a (node.value, MaxLimit do nó)

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; } 

Outra solução (se o espaço não for uma restrição): faça um percurso dentro da tree e armazene os valores do nó em uma matriz. Se a matriz está em ordem de sorting, é um BST válido caso contrário.

“Validar” uma tree de busca binária significa que você verifica se de fato tem todos os itens menores à esquerda e itens grandes à direita. Essencialmente, é uma verificação para ver se uma tree binária é uma tree de pesquisa binária.

A melhor solução que encontrei é O (n) e não usa espaço extra. É semelhante ao percurso in-order, mas em vez de armazená-lo em array e, em seguida, verificar se ele está classificado, podemos pegar uma variável estática e verificar enquanto a ordem é percorrida, quer o array esteja classificado.

 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; } 

Solução iterativa usando passagem interna.

 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; } 

Aqui está a minha solução no 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 a passagem em ordem de um BST é uma sequência não decrescente, poderíamos usar essa propriedade para julgar se uma tree binária é BST ou não. Usando a travessia de Morris e mantendo o nó pre , poderíamos obter uma solução em tempo O (n) e complexidade de espaço O (1) . Aqui está meu 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; } 

Aqui está a minha resposta em python, tem todos os casos de canto abordados e bem testados no site 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; } 

“É melhor definir um invariante primeiro. Aqui o invariante é – quaisquer dois elementos sequenciais do BST no percurso em ordem devem estar em ordem estritamente crescente de sua aparência (não pode ser igual, sempre aumentando em ordem Portanto, a solução pode ser apenas uma simples passagem em ordem com a lembrança do último nó visitado e a comparação entre o nó atual e o último visitado até ‘<' (ou '>‘). ”

 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) ) ) ); } 

Eu recebi essa pergunta em uma entrevista por telefone recentemente e lutei com ela mais do que deveria. Eu estava tentando manter o controle de mínimos e máximos em nós filhos e eu não conseguia envolver meu cérebro em torno dos diferentes casos sob a pressão de uma entrevista.

Depois de pensar sobre isso durante o sono na noite passada, percebi que é tão simples quanto acompanhar o último nó que você visitou durante uma travessia inorder. Em 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; } 

Em Java e permitindo nós com o mesmo valor em qualquer sub-tree:

 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 descobrir se determinado BT é BST para qualquer tipo de dados, você precisa ir com abordagem abaixo. 1. chame a function recursiva até o final do nó da folha usando a passagem de input 2. Crie você mesmo os valores mínimo e máximo.

O elemento da tree deve ter menos que / maior que o operador definido.

 #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 bem 🙂

A recursion é fácil, mas a abordagem iterativa é melhor, há uma versão iterativa acima, mas é complexa demais do que o necessário. Aqui está a melhor solução em c++ que você encontrará em qualquer lugar:

Esse algoritmo é executado no tempo O(N) e precisa de espaço 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; } 

Eu escrevi uma solução para usar inorder Traversal BST e verificar se os nós estão aumentando a ordem para o espaço O(1) e tempo O(n) . TreeNode predecessor é o nó prev. Não tenho certeza se a solução está certa ou não. Porque o inorder Traversal não pode definir uma tree inteira.

 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 seguir está a implementação Java da validação BST, na qual viajamos a tree em ordem DFS e retorna false se obtivermos qualquer número que seja maior que o ú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; } } 

Solução 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) } 

Solução 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; } 

Isso funciona para duplicatas.

 // 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) 

Isso funciona mesmo para valores int.max 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/

Existem duas soluções gerais: percorrer e dividir & & conquistar.

 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); } } 

Um forro

 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); } 

Linha bem longa embora.

Aqui está a solução iterativa sem usar espaço 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)); } 

Aqui está minha solução recursiva escrita em 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); }