How do you approach Validate Binary Search Tree?

Use recursion with min/max bounds for each node.

What is the time complexity of Validate Binary Search Tree?

Time complexity: O(n). Space complexity: O(h) where h is the height of the tree.

What are common mistakes on Validate Binary Search Tree?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Validate Binary Search Tree

MediumData Structures

Description

Given the `root` of a binary tree, determine if it is a valid binary search tree (BST). A **valid BST** is defined as follows: - The left subtree of a node contains only nodes with keys **less than** the node's key. - The right subtree of a node contains only nodes with keys **greater than** the node's key. - Both the left and right subtrees must also be binary search trees. **Note:** For this problem, the tree is represented as an array in level-order (BFS) format, where `null` represents missing nodes.

Example 1

Input: root = [2,1,3]

Output: true

Example 2

Input: root = [5,1,4,null,null,3,6]

Output: false

Explanation: The root node's value is 5 but its right child's value is 4.

Constraints

- The number of nodes in the tree is in the range [1, 10^4]. - -2^31 <= Node.val <= 2^31 - 1

Validate Binary Search Tree: approach, complexity and pitfalls

A medium trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

Use recursion with min/max bounds for each node.
For the left subtree, the max bound is the parent's value.
For the right subtree, the min bound is the parent's value.

The optimal approach

Show the approach: Recursive with Bounds

Pass min and max bounds during recursion. Each node must be within its bounds, and update bounds for children.

Time: O(n)
Space: O(h) where h is the height of the tree

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.