98. Validate Binary Search Tree

At a Glance

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

Problem (one-liner)

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).

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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