Data structures problem 26 of 30

Validate a binary search tree

Data structures
Hard

Write is_bst(root) that returns True if a binary tree is a valid binary search tree: for every node, all values in its left subtree are smaller and all values in its right subtree are larger.

#     5
#    / \
#   3   8
#    \
#     6
# is_bst(root) -> False: 6 is in 5's left subtree

Show hint

Checking each node against just its children is not enough, as the example shows. Pass down the range of values each subtree is allowed to contain.

Show solution

def is_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if not (low < node.val < high):
        return False
    return (is_bst(node.left, low, node.val)
            and is_bst(node.right, node.val, high))

Going left tightens the upper bound and going right tightens the lower bound, so every node is checked against all its ancestors, not just its parent. O(n) time. Another valid approach: an in-order traversal of a BST visits values in strictly increasing order.

Want a problem like this every day? See today's problem and keep a streak going.