Validate Binary Search Tree

Decide whether a binary tree is a valid BST: every left subtree holds smaller values and every right subtree holds larger values.

A way to picture it

Every node gets a permission slip from its ancestors: “you must be bigger than this and smaller than that.” Going left lowers the ceiling to the parent's value; going right raises the floor. A node outside its slip breaks the rules.

How to approach it

Pass down an open range (lo, hi). Each node must satisfy lo < val < hi; its left child gets (lo, val) and its right child gets (val, hi).

Example

Input: {"root":[2,1,3]}. Output: true.

Complexity: O(n) time and O(h) space. Each node is checked once against its range.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.