Trees: Is This a Binary Search Tree? Discussions |

4 years ago+ 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