Trees: Is This a Binary Search Tree?

  • + 2 comments

    A variation where a stack is used instead of recursion. I do not fancy recursion in Python as the maximum recursion depth is about 1000 per default. With the stack (a deque could also be used), you avoid a potential recursion limit error.

    With the stack, no helper method is needed either.

    def checkBST(root):
        if root is None:
            return True
        stack = [(float('-inf'), root, float('+inf'))]
        while stack:
            mind, node, maxd = stack.pop()
            if not (mind < node.data < maxd):
                return False
            if node.left is not None:
                stack.append((mind, node.left, node.data))
            if node.right is not None: 
                stack.append((node.data, node.right, maxd))
        return True