Pages

HackerRank Trees: Is This a Binary Search Tree?

As the title suggest, the point of this hackerrank problem is checking if a tree is a BST.

Before being able to work on this problem, you should know what we are talking about. In a few words, a BST is a tree in which for each node is true that its left children are strictly smaller and the right one are strictly bigger.

In Python, if a node is represented in this way
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
We can check a tree passing its root to a recursive function like this one:
def is_bst(node, left, right):  # 1
    if node is None:  # 2
        return True
    if not left < node.data < right:  # 3
        return False
    return is_bst(node.left, left, node.data) and is_bst(node.right, node.data, right)  # 4
1. The first parameter, node, is an instance of the class Node. The other two parameters are the limit in which the value is supposed to be. 2. An empty tree is a BST. This comes handy to manage the leaves of the tree. 3. The node value should lie in the specified interval, otherwise this is not a BST. 4. If the current node passes the check, we explore the rest of the tree. On the left we restrict the interval cutting it to the right, on the right we cut it on the left. Couple of questions. What should we pass as left and right for the root? And, What if we don't want to accept an empty tree as a valid BST? I think that in Python a good solution could be having a starting call like is_bst(root) that do not check for an interval and define on its own what to do in case of None. And then it call the above is_bst() for all the other nodes.

No comments:

Post a Comment