BST range bounds

33 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A binary search tree (BST) has one rule: for every node, everything in its left subtree is smaller than it, and everything in its right subtree is larger. Check this tree: 5 at the top; 1 on its left; 4 on its right; 3 and 6 under 4. Is it a BST?

A quick glance at each parent and its two children says yes: 1 < 5, 4 < 5... wait, 4 is on the right of 5 and 4 < 5. Already broken. But suppose the right child had been 7 with 3 and 8 under it. Then every parent-child pair looks fine (3 < 7 < 8, 1 < 5 < 7), yet 3 sits in the right subtree of 5 while being smaller than 5. The rule is about every ancestor, not just the parent. Checking each node against all its ancestors by hand costs up to h comparisons per node, roughly n × h in total.

Build the structure, one piece at a time

Piece one: an allowed range for every node, two numbers (low, high). The root may be anything: (−∞, +∞).

Piece two: how the range changes when you step down. Going to the left child, every value there must be smaller than the current node, so the high end becomes the current value. Going right, the low end becomes the current value. The range is handed down along with the recursion, exactly like the state in root-to-leaf problems.

Piece three: the check. At each node, test low < value < high. If it fails anywhere, the tree is not a BST. If it passes everywhere, it is.

In the second tree (7 on the right with 3 under it), 7 receives (5, ∞), passes, and hands 3 the range (5, 7). 3 is not inside, so the deep violation is caught too, without ever looking back at the ancestors.

Why it is correct

The invariant: the range handed to a node is exactly the set of values that all of its ancestors together allow. At the root no ancestor exists, so the range is everything. Stepping to a left child adds one constraint, "smaller than me", which intersects the old range with (−∞, value); stepping right intersects with (value, ∞). Intersecting intervals is what the two updates do.

range(v) = intersection over ancestors a of { (−∞, a) if v is left of a, (a, ∞) if right of a }

So "value inside its range" means "value satisfies every ancestor", which is the BST rule for that node. Checking it at every node checks the whole rule. Use strict inequalities so duplicate values are rejected, as the problems require.

Why it is fast

Each node receives two numbers and does two comparisons: O(n) time, O(h) stack. The by-hand method compared every node with every ancestor, O(n × h), which for a deep tree is close to n². Carrying the bounds compresses all the ancestors into two numbers.

How to recognise it in an interview

"Is this a valid BST", "sum of all values between L and R in a BST", "trim the BST to a range", "count subtrees whose values fit a bound". Say: "I will pass an allowed (low, high) range down the recursion, tightening one side at each step." Validate Binary Search Tree is this exactly, and the classic trap is checking only parent and child. Range Sum of BST uses the bounds the other way: because the tree is valid, a node below L has nothing useful on its left, so skip that side. Trim a Binary Search Tree cuts off a subtree the moment its root falls outside the range.

02The idea in one line

Pass (low, high) downward; a node must sit strictly inside.

Reach for it when: Validate BST, count nodes in range, range sum of BST.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Validate BST on [5,1,4,null,null,3,6]. These are its captions in order, so you can follow without the video or check a step you missed.

1. BST rule: every left descendant < node < every right descendant
2. Root gets the open range (−∞, ∞)
3. 5 is inside (−∞, ∞): ok
4. Left child 1 inherits (−∞, 5)
5. 1 is inside (−∞, 5): ok
6. Right child 4 inherits (5, ∞)
7. 4 is not inside (5, ∞): invalid BST
8. Checking only the parent is not enough; 3 < 5 breaks the root's rule
9. One pass carrying two bounds: O(n)

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Binary Search Tree: Inorder = sorted order, BST insert / delete / search, Build a balanced BST from sorted input.