How do you check binary search tree?

Question

I read an exercise in an interview here, known as checking the binary search tree.

How exactly does it work? What could one look for when checking a binary search tree? I wrote a basic search tree, but I never heard of this concept.

Answer 1

Actually, this is a mistake that everyone makes in the interview.

The left side should be marked against (minLimitof node, node.value)

Rightchild needs to be checked (node.value, MaxLimit 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; } 

Another solution (if space is not a limitation): Swipe the tree in order and store the node values ​​in an array. If the array is in sorted order, then its valid BST is otherwise not.

Answer 2

“Checking” the binary search tree means that you are checking that it really has all the small items on the left and large items on the right. Essentially, it is a test to find out if a binary tree is a binary search tree.

Answer 3

The best solution I found is O (n) and it does not use extra space. It looks like a workaround bypass, but instead of storing it in an array and then checking to see if it will be sorted, we can take a static variable and check while inorder crosses the array sort.

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

Answer 4

An iterative solution using a workaround.

 bool is_bst(Node *root) { if (!root) return true; std::stack<Node*> 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; } 

Answer 5

Here is my solution in 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))) 

Answer 6

Since traversal of a sequence in a BST is a sequence without reduction, we can use this property to determine if the binary tree is a BST or not. Using Morris traversal and supporting pre node, we could get a solution in O (n) time and O (1) space complexity . Here is my code

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

Answer 7

Here is my answer in python, it addresses all key cases and is well tested on the hackerrank site.

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

Answer 8

“It’s better to define the invariant first. Here the invariant is any two consecutive BST elements in a roundabout order should be in strictly increasing order of their appearance (cannot be equal, always increasing in in-order traversal). Thus, the solution can be just a simple roundabout in order to remember the last visited node and compare the current node with the last visited before '<' (or '>'). "

Answer 9

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

Answer 10

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

Answer 11

I recently got this question in a telephone interview and struggled with it more than I should have. I tried to track the lows and highs in the child nodes, and I just couldn't wrap my brain around different cases under pressure from the interview.

Thinking about it when he fell asleep last night, I realized that it was as easy as tracking the last node that you visited during the workaround. In Java:

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

Answer 12

In Java and resolving nodes with the same value in any of the subtrees:

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

Answer 13

Recursive solution:

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

Answer 14

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

Answer 15

To find out if a given BT BST is for any type of data, you need to go with the approach below. 1. call the recursive function to the end of the node sheet using a workaround 2. Create your minimum and maximum values ​​yourself.

The tree element must have less or more than what is defined by the operator.

 #define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal) #define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal) template <class T> bool IsValidBST (treeNode &root) { T min, max; return IsValidBST (root, &min, &max); } template <class T> 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; } 

Answer 16

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

It works well :)

Answer 17

Recursion is simple, but an iterative approach is better; there is one iterative version above, but it is too complex than necessary. Here is the best c++ solution you'll ever find:

This algorithm runs in O(N) time and needs an O(lgN) .

 struct TreeNode { int value; TreeNode* left; TreeNode* right; }; bool isBST(TreeNode* root) { vector<TreeNode*> 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; } 

Answer 18

I wrote a solution to use inorder Traversal BST and check if the nodes are in increasing order for O(1) space and O(n) . TreeNode predecessor - prev node. I am not sure if this is correct or not. Since traversal in order cannot determine the whole tree.

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

Answer 19

The following is a Java implementation for checking BST, where we move the tree in DFS order, and it returns false if we get any number that is larger than the last.

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

Answer 20

Iterative solution.

 private static boolean checkBst(bst node) { Stack<bst> s = new Stack<bst>(); 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; } 

Answer 21

This works for duplicates.

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

This works even for int.min and int.max values ​​using Nullable types.

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

Answer 22

Inspired by http://www.jiuzhang.com/solutions/validate-binary-search-tree/

There are two general solutions: bypass and division && win.

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

Answer 23

Single liner

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

Pretty long line though.

Answer 24

Here's a solution in Java from the sedgewick algorithm class. Check out the full BST implementation here

I have added some explanatory comments.

 private boolean isBST() { return isBST(root, null, null); } private boolean isBST(Node x, Key min, Key max) { if (x == null) return true; // when checking right subtree min is key of x parent if (min != null && x.key.compareTo(min) <= 0) return false; // when checking left subtree, max is key of x parent if (max != null && x.key.compareTo(max) >= 0) return false; // check left subtree and right subtree return isBST(x.left, min, x.key) && isBST(x.right, x.key, max); } 

Answer 25

• iterative function iterative checks if a given tree is a binary search tree.
• The recurse function recursively checks whether a given tree is a binary search tree or not.
• In the iterative function, I use BFS to check for BST.
• In the recurse function recurse I use dfs to test the BST.
• Both solutions have time complexity O(n)
• iterative solution takes precedence over the recurse solution, and this iterative solution makes an early stop.
• Even the recurse function can be optimized for an early stop by the global flag value.
• The idea of ​​both solutions is that the left child must range from -infinity to the value of its parent node, which is the root node.
• The right child should range from + infinity to the value of its parent node, which is the root node

• And keep comparing the current value of the node within the range. If any node value is not in the range, then return False

   class Solution: def isValidBST(self, root): """ :type root: TreeNode :rtype: bool """ return self.iterative(root) # return self.recurse(root, float("inf"), float("-inf")) def iterative(self, root): if not root: return True level = [[root, -float("inf"), float("inf")]] while level: next_level = [] for element in level: node, min_val, max_val = element if min_val<node.val<max_val: if node.left: next_level.append([node.left, min_val, node.val]) if node.right: next_level.append([node.right, node.val, max_val]) else: return False level = next_level return True def recurse(self, root, maxi, mini): if root is None: return True if root.val < mini or root.val > maxi: return False return self.recurse(root.left, root.val-1, mini) and self.recurse(root.right, maxi, root.val+1) 

Answer 26

Python implementation example. This example uses type annotations. However, since the Node class uses itself, we need to include as the first line of the module:

 from __future__ import annotations 

Otherwise, you will get the name 'Node' is not defined error. This example also uses the data class as an example. To check if this is a BST, it uses recursion to check the values ​​of the left and right nodes.

 """Checks if Binary Search Tree (BST) is balanced""" from __future__ import annotations import sys from dataclasses import dataclass MAX_KEY = sys.maxsize MIN_KEY = -sys.maxsize - 1 @dataclass class Node: value: int left: Node right: Node @property def is_leaf(self) -> bool: """Check if node is a leaf""" return not self.left and not self.right def is_bst(node: Node, min_value: int, max_value: int) -> bool: if node.value < min_value or max_value < node.value: return False elif node.is_leaf: return True return is_bst(node.left, min_value, node.value) and is_bst( node.right, node.value, max_value ) if __name__ == "__main__": node5 = Node(5, None, None) node25 = Node(25, None, None) node40 = Node(40, None, None) node10 = Node(10, None, None) # balanced tree node30 = Node(30, node25, node40) root = Node(20, node10, node30) print(is_bst(root, MIN_KEY, MAX_KEY)) # unbalanced tree node30 = Node(30, node5, node40) root = Node(20, node10, node30) print(is_bst(root, MIN_KEY, MAX_KEY)) 

Answer 27

Here is an iterative solution without using extra space.

 Node{ int value; Node right, left } public boolean ValidateBST(Node root){ Node currNode = root; Node prevNode = null; Stack<Node> stack = new Stack<Node>(); 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; } } 

Answer 28

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

Answer 29

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

Answer 30

Here is my recursive solution written in 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); }