Introduction

To check whether a binary tree is a binary search tree, you need to verify more than just each parent and its immediate children. The correct rule is global: every value in the left subtree must be smaller than the node, and every value in the right subtree must be larger, all the way down the tree.

Why local comparisons are not enough

A common wrong approach checks only this:

• left child value is smaller than the current node,
• right child value is larger than the current node.

That can fail on trees like this:

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

The node 6 is smaller than 15, so the local check passes, but it is in the right subtree of 10, so the whole tree is not a valid BST.

Correct solution: min/max bounds

The standard solution carries allowed value bounds down the recursion.

1class Node:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8def is_bst(node, low=float('-inf'), high=float('inf')):
9    if node is None:
10        return True
11
12    if not (low < node.value < high):
13        return False
14
15    return (
16        is_bst(node.left, low, node.value) and
17        is_bst(node.right, node.value, high)
18    )
19
20
21root = Node(10,
22            left=Node(5),
23            right=Node(15, left=Node(6), right=Node(20)))
24
25print(is_bst(root))

This correctly prints False because 6 violates the valid range for the right subtree of 10.

Alternative solution: in-order traversal

Another valid approach uses the fact that an in-order traversal of a BST visits values in sorted order.

1def is_bst_inorder(node):
2    values = []
3
4    def traverse(current):
5        if current is None:
6            return
7        traverse(current.left)
8        values.append(current.value)
9        traverse(current.right)
10
11    traverse(node)
12    return all(values[i] < values[i + 1] for i in range(len(values) - 1))

This is easy to understand, but it stores all visited values. The min/max approach is usually better because it validates on the fly and uses only recursion stack space.

Handling duplicates

Whether duplicates are allowed depends on the tree definition being used. Some BST definitions forbid duplicates entirely. Others allow them only on one side.

That choice changes the comparison rules. For example:

• strict BST: low < node.value < high
• duplicates on the right: left stays strict, right may use <=

The important thing is to make the rule explicit and then apply it consistently.

A good validator should also be easy to test. Include empty trees, single-node trees, valid balanced BSTs, invalid deep-descendant counterexamples, and whichever duplicate rule your implementation is supposed to honor. Those tests catch far more bugs than a single happy-path example. They also make duplicate-handling assumptions visible instead of leaving them implicit in the code. That makes future refactors much safer. Clear tests prevent subtle regressions.

Common Pitfalls

The biggest mistake is validating only parent-child relationships. A BST condition is global across subtrees, not local to one edge.

Another issue is forgetting to define how duplicates should behave. A validator that silently assumes one rule may reject trees built under another rule.

Be careful with integer edge cases in fixed-width languages. If you use sentinel values for minimum and maximum bounds, make sure they do not collide with real data.

Finally, recursive solutions are simple, but very deep trees can cause stack-depth issues. In those cases, an iterative in-order traversal with an explicit stack may be safer.

Summary

• A valid BST must satisfy subtree-wide ordering rules, not just local parent-child comparisons.
• The min/max bound approach is the standard correct solution.
• In-order traversal is another valid method when strictly increasing output is expected.
• Duplicate-handling rules must be defined explicitly.
• Test with counterexamples where a deep descendant violates an ancestor bound.