Given a Binary Tree, Check whether it is a BST or not.

What is a Binary Search Tree (BST) ?

A BST is a binary tree where each element in the left subtree is less than the root element and each element in the right subtree is greater than the root.

The initial approach that could come in your mind is to check if the left child is less than root and right child is greater than the root and check the same condition for all nodes. However this would be wrong, because the root must be greater than ALL the elements in the left, and you just compared with 1 element. Same goes for the right.

The beauty of tree structure is that if you understand recursion well, you can attempt any question on this topic. So Step 1 is to think in terms of Recursion for tree problems.

Approach

Root could have any value from -Infinity to +Infinity. But its left child should be between -Infinity to value of root and right child should be between value of root to +Infinity.

In the same way, if we go left in the recursion, the upper bound will be value of root, and if we go right in the recursion the lower bound will be the value of root. If all the node values are within their proper ranges, we have a BST !

Here is a link to the problem on Hackerrank.

Solution

Below is the python code which passed all test cases.

def checkBST(node, lmin, lmax):
    if node == None:
        return True
    else:
        if node.data > lmin and node.data < lmax:
            return checkBST(node.left, lmin, node.data)
             and checkBST(node.right, node.data, lmax)
        else:
            return False
def check_binary_search_tree_(root):
    return checkBST(root, 0, 10000);

Just check if the value at the node is within the range and pass on the recursion to left and right children by updating the range values, you have to return true if left sub tree is also a BST and right sub tree is also a BST and false otherwise.

Key Points To Remember

• Think in terms of recursion if you have a tree question. ✔
• Think of the base cases and pass on the recursion to left and right children. ✔

👏 Congrats! You just learned a frequently asked interview question.👏