Validating a Binary Search Tree

Carry the range that each node is allowed to fall into. A node's value must be strictly greater than every value in its ancestors' left subtrees and strictly less than every value in their right subtrees, so as you descend you tighten the bounds and check each node against them.

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


def is_valid_bst(root):
    def check(node, low, high):
        if node is None:
            return True
        if node.value <= low or node.value >= high:
            return False
        return check(node.left, low, node.value) and check(node.right, node.value, high)
    return check(root, float('-inf'), float('inf'))


print(is_valid_bst(TreeNode(2, TreeNode(1), TreeNode(3))))
print(is_valid_bst(TreeNode(5, TreeNode(1, TreeNode(6)), TreeNode(4))))

The outputs are True and False. The first tree has 1 on the left and 3 on the right of 2, which is correct. The second has a 4 in the right subtree of 5 and a 6 inside the left subtree, and both break the ordering.

The mechanism is that the bounds carry the constraints of all the ancestors at once. When you go left the upper bound becomes the current node's value, and when you go right the lower bound becomes it, so the check at each node automatically enforces every rule that applies to it.

The trade-off to name is the bounds approach uses strict comparisons, so duplicate values are rejected. Some definitions allow equal values on one side, and if you need that, one of the two comparisons becomes non-strict, but you have to decide which side is allowed to hold the duplicate and say so. The recursive version also uses stack space proportional to the height, so a skewed tree of a hundred thousand nodes would overflow, and an iterative version with an explicit stack of bounds would avoid that.

Because the search tree property is a constraint against every ancestor, not just the parent. A node can be smaller than its parent and still be larger than a value that belongs on the other side of an ancestor, which is exactly the case the parent check misses.

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


def naive_valid(root):
    def check(node):
        if node is None:
            return True
        if node.left and node.left.value >= node.value:
            return False
        if node.right and node.right.value <= node.value:
            return False
        return check(node.left) and check(node.right)
    return check(root)


tree = TreeNode(5, TreeNode(1, TreeNode(6)), TreeNode(4))
print(naive_valid(tree))

The output is True, and that is the problem. The tree is not a valid search tree, because the 4 sits in the right subtree of 5 and must be greater than 5, and the 6 sits in the left subtree and must be smaller than 5. The naive check only compares 1 with 5, 4 with 5 and 6 with 1, and every one of those comparisons passes.

The mechanism of the failure is that the parent check has no memory of the wider context. It knows the immediate relationship but not the accumulated range, so a violation that spans two levels is invisible to it.

The trade-off to name is that the naive version is linear in the number of nodes with constant space and no extra parameters, while the correct version needs to thread the bounds through the recursion. A third option avoids the bounds entirely: an inorder traversal of a valid search tree produces a strictly increasing sequence, so you can validate the tree by checking that. That version has the same complexity and is often the cleanest to write, and it is a good second answer to give when the interviewer wants to see more than one approach.