Is a Tree a valid Binary Search Tree?

Hacking the coding interviews at FAANG!

A binary tree is a tree in which each node has between 0–2 children. They’re called the left and right children of the node.

Problem Statement : Given a Binary Tree, figure out whether it’s a Binary Search Tree.

In a binary search tree, each node’s key value is smaller than the key value of all nodes in the right subtree, and are greater than the key values of all nodes in the left subtree.

The binary tree given above is a valid BST.

The binary tree above is not a valid BST (since 90<100).

Solution 1 :

There are several ways of solving this problem. A naïve algorithm would be to check on each node where the maximum value of its left sub-tree is less than the node’s data and the minimum value of its right sub-tree is greater than the node’s data. This is highly inefficient as for each node, both of its left and right sub-trees are explored.

Another approach would be to do a regular in-order traversal and in each recursive call, pass maximum and minimum bounds to check whether the current node’s value is within the given bounds. This approach is efficient compared to the one above.

Also, recursive solutions will demand your visualisation adeptness.

Here is an example of the latter approach: in-order traversal with limits on the value of the key.

Code(JavaScript)

let isBstRec = function(root, min_value, max_value) {
if (!root) {
return true;
}

//violation of min or max bounds
if (root.data < min_value || root.data > max_value) { 
return false;
}
//recursive calls for the left and right nodes 
return isBstRec(root.left, min_value, root.data) && isBstRec(root.right, root.data, max_value);
};
let isBst = function(root) { // main calling function
return isBstRec(root, -Number.MAX_VALUE - 1, Number.MAX_VALUE);
};

Runtime complexity : The runtime complexity of this solution is linear, O(n).

Memory complexity : The memory complexity of this solution is linear, O(n).

Recursive solution has O(h) memory complexity as it will consume memory on the stack up to the height of binary tree h. It will be O(logn) for a balanced tree and in the worst case can be O(n).

Solution 2

One nice property of a Binary Search Tree is that its inorder traversals are always sorted. We can use this property to check whether or not a given binary tree is a BST. Just do a regular inorder traversal and keep track of the last seen node (prev), then check whether the current node’s value is greater than or equal to the previous (prev) node’s value.

Code(JavaScript)

let prev = -1;  // stores the previous visited node value

let isBst = function(root) {      // main caller function
// assuming all tree values are positive.
prev = -1;
return isBstRec(root);
};
let isBstRec = function(root) {      // recursive function
if (!root) {      // end case
return true;
}

if (isBstRec(root.left) === false) { // first visit left subtree
return false;
}

if (prev > root.data && prev != -1) {  // condition violation
return false;
}
prev = root.data;  // updating previous node value

if (isBstRec(root.right) === false) { // visit right subtree
return false;
}
return true;  // if no violation return true
};

Runtime complexity : The runtime complexity of this solution is linear, O(n).

Memory complexity : The memory complexity of this solution is O(h).