Check if a binary tree is a binary search tree

Question

Given a binary tree, I need to check if it satisfies the binary search tree property i.e. left child is less than or equal to the current node and right child is greater than or equal to the current node.

from collections import namedtuple

Node = namedtuple('Node', 'key, left, right')

def is_bst(node, key_min=None, key_max=None):
    """Checks is the subtree rooted at this node is a BST."""
    if node is None:
        return True # By definiton
    if key_max is not None and node.key >= key_max:
        return False
    if key_min is not None and  node.key <= key_min:
        return False
    return is_bst(node.left, None, node.key) and is_bst(node.right, node.key, None)

import unittest

class TestBst(unittest.TestCase):
    def test_none(self):
        self.assertTrue(is_bst(None))

    def test_left_skewed(self):
        root = Node(8, Node(3, Node(1, None, None), None), None)
        self.assertTrue(is_bst(root))    

    def test_right_skewed(self):
        root = Node(8, None, Node(10, None, Node(14, None, None)))
        self.assertTrue(is_bst(root))

    def test_bst(self):
        root = Node(8, Node(3, None, None), Node(10, None, None))
        self.assertTrue(is_bst(root))

    def test_non_bst(self):
        root = Node(8, Node(10, None, None), Node(6, None, None))
        self.assertFalse(is_bst(root))

if __name__ == '__main__':
    unittest.main()

I want to know if I can convert it to an iterative version. If yes, then how?

Time complexity

The algorithm visits each node exactly once, hence the complexity should be \$\Theta(n)\$, where \$n\$ is the number of node in the tree.

Answer 1

I think one of reasons that this question is on the verge of getting closed, is that the code presented doesn't make much sense combined with a question of iterative version. But let us come to back that.

Code and style review

• Good naming of methods and variables – You are trying to follow the PEP8 and that is good
• Combine similar if statements – When you have similar if condition, and they do the same, then combine them using the or operator
• Use \ (line continuation) or parenthesis to break long if conditions – This is a matter of personal preferences, and one area where I'm not sure what I prefer to do in all cases. But if you have a long if condition, you can either break it using a single \ at the end of the line, or add the otherwise unneccessary parenthesis around the entire condition.
• Add vertical space between non-similar if statements – In some places it can be good to introduce a little vertical space. This is especially true with following if/elif/else blocks. If not vertically spaced, one might wonder if they should have been using elif or else instead. And if they really are meant to be separate if statements, then separate them using extra newlines. This enhance readability, and code understanding

• (optional) Shorten None conditions – Consider whether you want to test directly on not node or if you want to use the more verbose node is None. In most cases they are identical, but I tend to prefer the not node version my self.

• Bug: Not keeping the key_min and key_max whilst traversing tree – Your code sets these to None, which would introduce errors if you have a tree with a little more levels then your test case, and you first traverse a left tree, and then go down the right tree. That value could now be higher than the root value, and you'll be happy with that. So extend test cases, and then afterwards correct the bug.

   

With these options implemented you'll get the following (untested) code:

def is_bst(node, key_min=None, key_max=None):
    """Checks is the subtree rooted at this node is a BST."""
    if node is None:
        return True 

    if (not key_max and node.key >= key_max) \
        or (not key_min and node.key <= key_min):

        return False

    return is_bst(node.left, key_min, node.key) \
           and is_bst(node.right, node.key, key_max)

Algorithmic comments

Your implementation is good, and should do what it is supposed, with correction of bug, and does so in a recursive manner. You can't do it entirely iterative as retrieving the values of a tree is not an iterative procedure.

However, you do have the option of creating/returning/yielding something which you can use in an iterative manner. Either iterating over your returned list from inorder(), or by implementing an iterative version of the traversal, as I've done in my answer for values_in_order().

If having some you can iterate over you could do either of the following variants:

# First variant: Manually keeping the previous_node
previous_node = None
for node in inorder(root):
    if previous_node and previous_node.key > node.key:
        return False
    previous_node = node

# Second variant: Using the itertools.pairwise iterator
return any(prev.key > node.key for prev, node in pairwise(inorder(root)))

The last one depending on the itertools.pairwise recipe, which returns all pairs of nodes from the start through end.

Do however note, that neither of these methods are tested for efficiency or speed, but are mostly presented as alternate methods on how to do the check whether all the values are in sorted order which seems to the criteria for a binary search tree.

Answer 2

Another solution without using None. Using None create confusions and forces us to write extra conditional codes.

from collections import namedtuple

Node = namedtuple('Node', 'key, left, right')

def is_bst(node, key_min=float("-inf"), key_max=float("inf")):
    """Checks if the subtree rooted at this node is a BST."""
    if node is None:
        return True # By definiton
    if node.key <= key_max and node.key >= key_min:
        return is_bst(node.left, key_min, node.key) and\
            is_bst(node.right, node.key, key_max)
    else:
        return False

if __name__ == '__main__':
    import unittest

    class TestBst(unittest.TestCase):
        def test_none(self):
            self.assertTrue(is_bst(None))

        def test_left_skewed(self):
            """
                    8
                   / \
                  3   *
                 / \
                1   *
               / \
              *   * 
            """
            root = Node(8, Node(3, Node(1, None, None), None), None)
            self.assertTrue(is_bst(root))    

        def test_right_skewed(self):
            """
                    8
                   / \
                  *  10
                     / \
                    *  14
            """
            root = Node(8, None, Node(10, None, Node(14, None, None)))
            self.assertTrue(is_bst(root))

        def test_bst(self):
            """
                    8
                   / \
                  3  10
                 / \ / \
                *  * *   *
            """
            root = Node(8, Node(3, None, None), Node(10, None, None))
            self.assertTrue(is_bst(root))

        def test_non_bst(self):
            """
                    10
                   /  \
                  5   15
                 / \  / \
                *   *6   20
                    / \  / \
                   *   **   *
            """
            root = Node(10,
                Node(5, None, None),#left subtree
                Node(15,            #right subtree
                    Node(6, None, None), Node(20, None, None)))
            self.assertFalse(is_bst(root))

    unittest.main()