Check if the binary tree is a binary search tree (Question 4.5 from "Cracking the coding Interview" book)

validate_bst.py

class BinaryTreeNode:
    
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        "insert elements in the way to maintain binary search tree structure"
        if self.value >= value:
            if self.left is None:
                self.left = BinaryTreeNode(value)
            else:
                self.left.insert(value)
        else:
            if self.right is None:
                self.right = BinaryTreeNode(value)
            else:
                self.right.insert(value)
    
    def random_insert(self, value):
        "insert new element to a leftmost part of an array (needed just to break structure of BST)"
        
        import numpy as np
        insert_left = bool(np.random.randint(2))
        
        if insert_left:
            if self.left is None:
                self.left = BinaryTreeNode(value)
            else:
                self.left.random_insert(value)
        else:
            if self.right is None:
                self.right = BinaryTreeNode(value)
            else:
                self.right.random_insert(value)
        return   
    
    def print(self):
        "in-order printing"
        if self.left is not None:
            self.left.print()
        print(self.value)
        if self.right is not None:
            self.right.print()

def validate_bst(bt, min_el=None, max_el=None):
    """Check if binary tree is a binary search tree.
    
    Definition of a binary search tree: for any node the following holds
        
        value(left_descendants_of_i) <= value(i) < value(right_descendants_of_i)
        
    Algorithm.
    
            10
        5       19
    2     8   12   28
    Yes
    In-order traversal: 2 5 8 10 12 19 28
    
            10
       17        19
    2     18   12   28
    No (18>10)
    In-order traversal: 2 17 18 10 12 19 28
    
            10
        5        10
    2     18   12   28
    No (10>=10)
    In-order traversal: 2 5 10 10 12 19 28
    
        10
       9
      8
     7
    6
    Yes
    In-order traversal: 6 7 8 9 10
    
            10
        5        10
    2     18   12   28
    No (10>=10)
    
        10
    
    node-5: min: null, max=10
    left-18: min: 5, max=10
    
    Algo #1. Brute force: check for every element if the condition holds. Complexity: n*avg_number_of_descendants
    
    Algo #2. Traverse binary tree: for ever subtree, keep track of min and max elements allowed
    """
    
    if bt is None:
        return True
    
    if bt.left is not None:
        if max_el is None:
            max_left = bt.value
        else:
            max_left = max(max_el, bt.value)
        if not validate_bst(bt.left, min_el=min_el, max_el=max_left):
            return False
    
    if (max_el is not None) and (bt.value > max_el):
        print("min_el: %s, max_el: %s, current element: %s" %(min_el, max_el, bt.value))
        return False
    if (min_el is not None) and (bt.value <= min_el):
        print("min_el: %s, max_el: %s, current element: %s" %(min_el, max_el, bt.value))
        return False
    
    if bt.right is not None:
        if min_el is None:
            min_right = bt.value
        else:
            min_right = min(min_el, bt.value)
        if not validate_bst(bt.right, min_el=min_right, max_el=max_el):
            return False
    
    return True


# DEMO

# Valid BST
bt = BinaryTreeNode(10)
bt.insert(19)
bt.insert(3)
bt.insert(19)
bt.insert(11)
bt.insert(1)
bt.print()
print("Valid BST: %s" % validate_bst(bt))

# Invalid BST
bt = BinaryTreeNode(10)
bt.insert(3)
bt.insert(19)
bt.insert(11)
bt.insert(1)
bt.random_insert(91)
bt.random_insert(8)
bt.print()
print("Valid BST: %s" % validate_bst(bt))