I read on here of an exercise in interviews known as validating a binary search tree.
How exactly does this work? What would one be looking for in validating a binary search tree? I have written a basic search tree, but never heard of this concept.
33 Answers
Actually that is the mistake everybody does in an interview.
Leftchild must be checked against (minLimitof node,node.value)
Rightchild must be checked against (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;
}
Another solution (if space is not a constraint): Do an inorder traversal of the tree and store the node values in an array. If the array is in sorted order, its a valid BST otherwise not.
"Validating" a binary search tree means that you check that it does indeed have all smaller items on the left and large items on the right. Essentially, it's a check to see if a binary tree is a binary search tree.
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 [[a b]] (< a b))
(partition 2 1 col)))
(defn is-valid-BST [bst]
(is-strictly-sorted? (in-order bst)))
One 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.
Here's a solution in java from sedgewick's algorithm class. Check the full BST implementation here
I 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's parent
if (min != null && x.key.compareTo(min) <= 0) return false;
// when checking left subtree, max is key of x's 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);
}
- The
iterativefunction checks iteratively whether given tree is a binary search tree. - The
recursefunction checks recursively whether given tree is a binary search tree or not. - In
iterativefunction I use bfs for checking BST. - In
recursefunction I use dfs for checking BST. - Both solutions have a time complexity of
O(n) iterativesolution has an advantage overrecursesolution and that isiterativesolution does early stopping.- Even
recursefunction can be optimized for early stopping by global flag value. - The idea of both the solution is that the left child should be within the range of -infinity to the value of its parent node whihch is the root node
- The right child should be within the range of +infinity to the value of its parent node whihch is the root node
And go on comparing the current node's value within the range. If any node's 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)
Python implementation example. This example uses type annotations. However since Node class uses itself we need to include as a first line of the module:
from __future__ import annotations
Otherwise, you will get name 'Node' is not defined error. This example also uses dataclass as an example. To check if it's BST it uses recursion for checking left and right nodes values.
"""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))
BST example
public bool IsBinarySearchTree(TreeNode root)
{
return IsValid(root, long.MinValue, long.MaxValue);
}
private static bool IsValid(TreeNode node, long min, long max)
{
if (node == null)
{
return true;
}
if (node.Value >= max || node.Value <= min)
{
return false;
}
return IsValid(node.Left, min, node.Value) && IsValid(node.Right, node.Value, max);
}
where TreeNode
public class TreeNode
{
public int Value;
public TreeNode Left;
public TreeNode Right;
public TreeNode(int value)
{
Value = value;
}
}
here's the detailed explanation https://codestandard.net/articles/validate-binary-search-tree/
We have to recursively ask each node if its left branch and right branch are valid binary search trees. The only thing each time we ask, we have to pass correct left and right boundaries:
class Solution:
def is_bst(self,root:TreeNode):
if not root:
return True
# left and right are boundaries
def dfs(node,left,right):
if not node:
return True
if not (node.val>left and node.val<right):
return False
# when we move right, we update the left, when we move left we update the right
return dfs(node.left,left,node.val) and dfs(node.right,node.val,right)
return dfs(root, float("-inf"), float("+inf"))
Using inOrder Traversal..
First Adding the tree value to the array with inorder traversal.
Then iterate through the array which add a flag value true to split the elements after the root elements and before the root elements.
counter is added to check if the tree has elements with the same root value.
min and max is set to the range
var isValidBST = function(root)
{
if(!root) return false;
let current = root;
let data = [];
let flag = false;
let counter = 0;
function check(node){
if(node.left){
check(node.left);
}
data.push(node.val);
if(node.right){
check(node.right);
}
}
let min = Number.MIN_SAFE_INTEGER;
let max = root.val;
for(let i = 0; i < data.length; i++){
if(data[i] == root.val){
flag = true;
counter++;
}
if(flag){
if(data[i] < root.val || data[i] < max || counter > 1){
return false;
}
else{
max = data[i];
}
}
else{
if(data[i] > root.val || data[i] <= min|| counter > 1){
return false
}
else {
min = data[i]
}
}
}
return true;
};
Here is the 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;
}
}
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));
}
Related