Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Validate Binary Search Tree

LeetCode #98Medium

Carry (low, high) bounds down

Given the root of a binary tree, determine whether it is a valid binary search tree, where every node in a left subtree is strictly less than its parent and every node in a right subtree is strictly greater.

Asked atAmazonMetaMicrosoft

Brute force (each node vs subtree min/max)

time O(n²)space O(h)

step 1 / 28

binary tree

call stack ↓

(returned)

Brute force (each node vs subtree min/max)


▸
1isValid(root):
2    for each node:
3        if max(left subtree) >= node or min(right subtree) <= node: return false
4    return true

state

ideamax(left subtree) < node < min(right subtree)

line 1Brute force: for EVERY node, scan its entire left subtree and confirm all values are smaller, then scan its entire right subtree and confirm all are larger. Correct, but each node re-walks its descendants — O(n²).