Check whether a binary tree is a binary search tree or not.

is_binary_tree_a_bst.py

"""
https://scammingthecodinginterview.com
Week 2: Trees
Problem: 3
"""


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


class Solution(object):

    def solve(self, root):

        return self.helper(root, (None, None))

    def helper(self, node, range):

        if not node:
            return True

        if range:
            if range[0]:
                status1 = range[0] <= node.data
            else:
                status1 = True

            if range[1]:
                status2 = node.data < range[1]
            else:
                status2 = True

            status = status1 and status2

        else:
            status = True

        range_left = (range[0], node.data)
        range_right = (node.data, range[1])

        if not status:
            return status
        else:
            return self.helper(node.left, range_left) and self.helper(node.right, range_right)


if __name__ == "__main__":

    root = Node(10)
    root.left = Node(7)
    root.right = Node(39)
    root.left.right = Node(8)

    ans = Solution().solve(root)

    print(ans)