Check if a tree is a BST or not

Medium

Carry a valid range down, not just the parent

Problem

Return whether a binary tree is a valid BST (left < node < right for every node, using value ranges).

In simple words

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

The idea

Comparing a node only with its children is not enough — a deep node can violate an ancestor's bound. Pass a (min, max) range down, tightening it at each step, so every node is checked against every ancestor that constrains it.

The trick

Going left tightens the max; going right tightens the min.
Start with an unbounded range at the root.
Equivalently: an in-order traversal must be strictly increasing.

←→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.