Validate Binary Search Tree

Medium

Carry a valid range downward

Problem

Return whether a binary tree is a valid BST using value ranges.

In simple words

Carry an allowed (low, high) range down each branch; every node must stay strictly inside it.

The idea

Checking a node against its immediate children is not enough, because a deep node can still violate a distant ancestor. Passing a (min, max) range down and narrowing it at each step enforces every ancestor's constraint at once.

The trick

Left child tightens the maximum, right child tightens the minimum.
Start unbounded at the root.
An in-order traversal must be strictly increasing — an equivalent check.

←→stepspaceplay

1/9

Optimal

timeO(n)spaceO(h)

Shrink bounds as you descend.

1function valid(node, low, high) {2  if (!node) return true;3  if (node.val <= low || node.val >= high) return false;4  return valid(node.left, low, node.val)5      && valid(node.right, node.val, high);6}

Input

nodes: 7, 6 edges

Memory

range: —

Output

valid: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: tree = [2,1,3]
Output:: true
Explanation:: Left < root < right everywhere.

Example 2

Input:: tree = [5,1,4,null,null,3,6]
Output:: false
Explanation:: 4 sits right of 5 but is smaller → false.

Example 3

Input:: tree = [1]
Output:: true
Explanation:: A single node is a valid BST.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.