Is this a valid binary search tree?

Pass an allowed range down the tree. The root may be anything; a left child must be below its parent and above the parent's own lower limit, and the right side mirrors that. Any node outside its range fails. O(n) time, O(h) stack.

Checking only parent and child is the classic wrong answer: a deep left descendant can still be bigger than the root.

Equivalent check: an in-order walk must be strictly increasing.

Use infinities (Python) or Long limits (Kotlin) so Int.MIN_VALUE and Int.MAX_VALUE values work.

def is_search_tree(root: Node | None) -> bool:
    def ok(node: Node | None, low: float, high: float) -> bool:
        if node is None:
            return True
        if not low < node.val < high:
            return False
        return (ok(node.left, low, node.val)
                and ok(node.right, node.val, high))
    return ok(root, float("-inf"), float("inf"))

fun isSearchTree(root: Node?): Boolean {
    fun ok(node: Node?, low: Long, high: Long): Boolean {
        if (node == null) return true
        if (node.value <= low || node.value >= high) return false
        return ok(node.left, low, node.value.toLong()) &&
            ok(node.right, node.value.toLong(), high)
    }
    return ok(root, Long.MIN_VALUE, Long.MAX_VALUE)
}

Common mistakes

• Comparing each node only with its direct children.
• Allowing duplicates without asking whether the tree permits them.

Draw the counterexample (a big value deep on the left) before you code. It shows why the range is needed.

Follow-up questions

Think of your answer first, then open the hint.

1. What if duplicates go to the left?

   Show hint

   Make the left bound inclusive: low < val <= high on that side.

2. How would you fix a tree where two values were swapped?

   Show hint

   Walk in order, find the two out-of-order spots, swap them back.