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.