DSA problem
Validate Binary Search Tree
Given the root of a binary tree, determine whether it is a valid Binary Search Tree (BST). A valid BST is defined as a tree in which the left subtree of every node contains only nodes with values strictly less than the node's value, the right subtree contains only nodes with strictly greater values, and both subtrees are themselves valid BSTs.
A common but wrong approach checks only node.left.val < node.val < node.right.val at each node. That is insufficient: a deeply-nested left descendant might still be greater than an ancestor's value. The validation must enforce the BST property across the entire subtree rooted at each node, not just its immediate children.
The cleanest correct algorithm exploits the inorder property of BSTs: a tree is a valid BST if and only if its inorder traversal produces a strictly increasing sequence. We can therefore walk the tree in inorder, keep one variable prev holding the value of the previously visited node, and fail as soon as we see a node whose value is not strictly greater than prev. If we finish the walk without failing, the tree is valid.
An alternative is the recursive range check: each node carries an allowed open interval (lo, hi) it must respect, and the left child inherits (lo, node.val) while the right inherits (node.val, hi). Both algorithms are O(n) time and O(h) space. The inorder version is preferred here because it leverages the very property the category is built around.
Examples
root = [2,1,3]trueroot = [5,1,4,null,null,3,6]falseroot = [2,2,2]falseConstraints
- The number of nodes in the tree is in the range [1, 10^4].
- -2^31 <= Node.val <= 2^31 - 1
- BST inequalities are strict (no equal values allowed).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.