We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Tutorials
  3. Cracking the Coding Interview
  4. Trees: Is This a Binary Search Tree?
  5. Discussions

Trees: Is This a Binary Search Tree?

  • Slaunger + 0 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