Introduction

Validating a binary search tree means checking more than whether each node is larger than its left child and smaller than its right child. A correct validator must prove that every value in the entire left subtree is less than the node and every value in the entire right subtree is greater.

Understand the BST Rule Precisely

For a tree to be a valid binary search tree, each node must satisfy a global ordering constraint:

• All values in the left subtree are smaller than the current node.
• All values in the right subtree are larger than the current node.
• The same rule must hold recursively for every subtree.

That “global” part is where many incorrect solutions fail. Consider this tree:

1    10
2   /  \
3  5    15
4      /  \
5     6    20

6 is less than 15, so a local child check would accept it, but it still violates the BST property because it appears in the right subtree of 10 and should therefore be greater than 10.

Validate with Lower and Upper Bounds

The most reliable approach is to pass an allowed value range down the tree.

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7
8def is_valid_bst(node, low=None, high=None):
9    if node is None:
10        return True
11
12    if low is not None and node.val <= low:
13        return False
14    if high is not None and node.val >= high:
15        return False
16
17    return (
18        is_valid_bst(node.left, low, node.val) and
19        is_valid_bst(node.right, node.val, high)
20    )
21
22
23root = TreeNode(10,
24    left=TreeNode(5),
25    right=TreeNode(15, TreeNode(12), TreeNode(20))
26)
27
28print(is_valid_bst(root))

This works because each recursive call tightens the allowed interval. A node in the right subtree inherits the parent’s lower bound, and a node in the left subtree inherits the parent’s upper bound.

The time complexity is O(n) because each node is visited once. The extra space is O(h) for the recursion stack, where h is the tree height.

In-Order Traversal as an Alternative

A second valid strategy uses the fact that an in-order traversal of a BST produces values in strictly increasing order.

1def is_valid_bst_inorder(root):
2    stack = []
3    current = root
4    previous = None
5
6    while stack or current:
7        while current:
8            stack.append(current)
9            current = current.left
10
11        current = stack.pop()
12
13        if previous is not None and current.val <= previous:
14            return False
15
16        previous = current.val
17        current = current.right
18
19    return True

This iterative version avoids recursion and is often useful in languages or environments where deep recursion is undesirable.

The in-order approach is elegant, but the bounds approach is usually easier to explain when teaching the core invariant directly.

Decide How to Handle Duplicates

Some BST definitions allow duplicates on one side only, while others require strict ordering with no duplicates at all. The comparison operators in your validator must match the definition your problem expects.

The examples above use strict comparisons:

• Left side must be strictly less than the parent.
• Right side must be strictly greater than the parent.

If duplicates are allowed on one side, change the comparison logic intentionally rather than by accident.

Why Local Checks Are Not Enough

A tempting but incorrect solution is:

1def wrong_validator(node):
2    if node is None:
3        return True
4    if node.left and node.left.val >= node.val:
5        return False
6    if node.right and node.right.val <= node.val:
7        return False
8    return wrong_validator(node.left) and wrong_validator(node.right)

This fails because it compares each node only with its immediate children. BST validity depends on all ancestors, not just the parent.

Common Pitfalls

The most common bug is validating only parent-child relationships instead of carrying full lower and upper bounds through recursion.

Another issue is handling duplicates incorrectly. If the problem expects a strict BST, use <= and >= in the failure conditions, not just < and >.

People also forget that an empty tree is a valid BST. Returning False for None breaks many otherwise correct recursive solutions.

Finally, watch out for hard-coded numeric sentinels such as minimum and maximum integers. Using None for unbounded ranges is often cleaner and avoids accidental overflow assumptions.

Summary

• A valid BST must satisfy ordering rules across entire subtrees, not just direct children.
• The bounds-based recursive solution is the most reliable general approach.
• An in-order traversal works because BST values appear in strictly increasing order.
• Duplicate handling depends on the exact BST definition in the problem.
• Empty trees are valid, and local child checks alone are not sufficient.