98. Validate Binary Search Tree

Quick Identifier

• Topic: trees
• Pattern: Tree DFS with bounds
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• Frequency: Very High
• LeetCode: 98

Quick Sights

• Time Complexity: O(n) from the optimal approach.
• Space Complexity: (minBound, maxBound) from the optimal approach.
• Core Mechanism: Given the root of a binary tree, return whether it is a valid BST: for every node, all values in the left subtree are strictly smaller and all values in the right subtree are strictly greater than the node’s value (common LeetCode definition).

Concept Explanation

Given the root of a binary tree, return whether it is a valid BST: for every node, all values in the left subtree are strictly smaller and all values in the right subtree are strictly greater than the node’s value (common LeetCode definition).

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• "Valid BST" — not just compare node to immediate children
• Need global lower/upper bounds per subtree
• Inorder sorted check is equivalent alternative

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — for each node, compute min/max of left and right subtrees independently — O(n²).
• Better — inorder traversal, check strictly increasing list — O(n) time / O(h) stack + could use O(1) extra if iterative with last-value pointer.
• Optimal — O(n) DFS with (minBound, maxBound) open bounds — O(h) stack — pass down allowed interval for each node’s key.

Optimal Solution

Go

package main

import "math"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
	var validate func(*TreeNode, int64, int64) bool
	validate = func(node *TreeNode, minBound int64, maxBound int64) bool {
		if node == nil {
			return true
		}
		value := int64(node.Val)
		if value <= minBound || value >= maxBound {
			return false
		}
		return validate(node.Left, minBound, value) && validate(node.Right, value, maxBound)
	}
	return validate(root, math.MinInt64, math.MaxInt64)
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function isValidBST(root) {
	function validate(node, minBound, maxBound) {
		if (node === null) {
			return true;
		}
		if (node.val <= minBound || node.val >= maxBound) {
			return false;
		}
		return (
			validate(node.left, minBound, node.val) &&
			validate(node.right, node.val, maxBound)
		);
	}
	return validate(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY);
}

Walkthrough

Preorder array [5,1,4,null,null,3,6] builds: root 5, left 1, 1’s right 4, 4’s left 3, 4’s right 6.

Invariant: every visited key must stay strictly inside the interval inherited from ancestors; recursion shrinks the interval at each step.

Valid tiny tree 2/1,3: each node stays inside its interval; DFS returns true.

Edge Cases

• Duplicate values — problem uses strict inequality; equal keys invalid except sometimes definition differs (read statement)
• int min/max bounds — use int64 in Go to compare safely vs math.MaxInt32 edge nodes

Pitfalls

• Checking only parent-child locally (node.Left.Val < node.Val < node.Right.Val) — fails for deeper violations
• Integer overflow on bounds — use wider type / nullable bounds pattern

Similar Problems

• 230. Kth Smallest Element in a BST — valid BST enables inorder k-th.
• 235. Lowest Common Ancestor of a BST — exploits ordering.
• 173. Binary Search Tree Iterator — inorder on valid BST.

Variants

• Allow duplicates in left or right by policy (LeetCode variants).
• Validate BST with parent pointers only.

Mind-Map Tags

#trees #bst #dfs #bounds #interval-validation