LeetCode #98 Medium

Validate Binary Search Tree

Is the tree a valid BST? Every node must exceed ALL left descendants and be below ALL right ones.

bstdfsrecursion

02

Intuition

💡

Checking only parent vs children misses violations deep in a subtree. Carry (min, max) bounds down instead: entering a left child caps the max at the parent; a right child raises the min. Each node checks itself against bounds inherited from every ancestor at once.

03

Approach

1

The classic wrong answer

node.left.val < node.val < node.right.val locally is NOT enough — a grandchild can violate a grandparent (e.g. [5,4,6,null,null,3,7], the 3 under 6).

2

Bounds propagation

valid(node, lo, hi): require lo < node.val < hi; recurse left with hi=node.val, right with lo=node.val.

3

Alternative: inorder

A BST's inorder is strictly increasing; traverse and compare consecutive values — same O(n).

04

Solution & live demo

python

▶1class Solution:
▶2    def isValidBST(self, root):
▶3        def valid(node, lo, hi):
▶4            if not node: return True
▶5            if not (lo < node.val < hi): return False
▶6            return (valid(node.left, lo, node.val)
▶7                    and valid(node.right, node.val, hi))
▶8        return valid(root, float("-inf"), float("inf"))

05

Edge cases

Duplicate value in a subtree

Strict inequalities reject equality — duplicates invalidate.

Int-extreme node values

±∞ initial bounds avoid sentinel-value collisions.

06

Complexity

Time

O(n)

Space

O(h)

Every node checked once against inherited bounds.