DSA · Trees · #184
Validate Binary Search Tree
Module 44 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given the `root` of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: - The left subtree of a node contains only nodes with keys **strictly less than** the node's key. - The right subtree of a node contains only nodes with keys **strictly greater than** the node's key. - Both the left and right subtrees must also be binary search trees. Each node is `{ val, left, right }` with `null` children. Implement `isValidBST(root)` returning a boolean. The empty tree (`root === null`) is valid.
Examples
root = [2,1,3]→true— Root 2 with left child 1 and right child 3 — every node respects the BST ordering.root = [5,1,4,null,null,3,6]→false— Root is 5 but its right child 4 is less than 5, violating the BST property.root = [10,5,15,null,null,6,20]→false— 6 sits in the right subtree of 10 but is less than 10, so it is out of the allowed (10, 15) range.
Constraints
- · The number of nodes is in the range [0, 10^4].
- · -2^31 <= Node.val <= 2^31 - 1
- · Node values may equal the integer bounds, so use unbounded sentinels (null/Infinity) rather than fixed min/max.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.