loading

Validate Binary Search Tree — Step-by-Step Visualization

mediumLeetCode #98TreeDepth-First SearchBinary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: (1) The left subtree of a node contains only nodes with keys less than the node's key. (2) The right subtree of a node contains only nodes with keys greater than the node's key. (3) Both the left and right subtrees must also be binary search trees.

Algorithm Pattern

Recursive Boundary Check

Key Idea

A common mistake is only checking if a child's value is less/greater than its parent. However, in a BST, *all* nodes in the left subtree must be less than the root, and *all* nodes in the right subtree must be greater. We solve this by passing down a `min` and `max` range that each node must fall within.

Step-by-Step Approach

  1. Initialize `dfs(node, min, max)` with `(-Infinity, +Infinity)`.
  2. Base Case: If `node` is null, it's valid. Return `true`.
  3. Check: If `node.val <= min` or `node.val >= max`, it's an invalid BST. Return `false`.
  4. Recurse Left: Update `max` to `node.val` and call `dfs(node.left, min, node.val)`.
  5. Recurse Right: Update `min` to `node.val` and call `dfs(node.right, node.val, max)`.

Common Gotchas

  • Wait, don't the values have to be strictly less/greater? Yes, `node.val <= min` or `node.val >= max` handles this.
  • Initial bounds should be use large enough values (or `null`/`undefined`) to represent infinity.

Related Problems

← All problems