DSA · Trees · #05

Validate Binary Search Tree

Module 7 · 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: - 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 BSTs. (Equal values are NOT allowed in a strict BST. Confirm this assumption.)

Examples

root = [2,1,3] → true
root = [5,1,4,null,null,3,6] → false — 4 is in the right subtree of 5, but 3 < 5
root = [2,2,2] → false — strict BST disallows duplicates

Constraints

· Number of nodes in [1, 10^4].
· -2^31 <= Node.val <= 2^31 - 1

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.