Skip to main content

61. Validate Binary Search Tree

mediumAsked at Datadog

Determine if a binary tree satisfies BST properties. Datadog asks this for the bounds-passing recursion pattern — same shape as validating an ordered range invariant on a hierarchical metric store.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite BST validation.
  • Blind (2025-11)— Recurring Datadog problem.

Problem

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.

Constraints

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

Examples

Example 1

Input
root = [2,1,3]
Output
true

Example 2

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

Explanation: Right subtree's root 4 < parent 5; violates BST.

Approaches

1. Compare each node to its immediate children

At each node, check left.val < node.val < right.val.

Time
O(n)
Space
O(h)
// WRONG. Doesn't catch [5,1,7,null,null,4,9] where 4 < 5 violates BST despite 4 < 7.

Tradeoff: Wrong. Datadog will fail you immediately for this — BST is a global property.

2. Bounds-passing recursion (optimal)

Recurse with (lo, hi) bounds. Each node must satisfy lo < val < hi. Left subtree gets (lo, val), right gets (val, hi).

Time
O(n)
Space
O(h)
function isValidBST(root) {
  function valid(node, lo, hi) {
    if (!node) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return valid(node.left, lo, node.val) && valid(node.right, node.val, hi);
  }
  return valid(root, -Infinity, Infinity);
}

Tradeoff: Correct. The bounds enforce the global BST property — every descendant must respect ancestor constraints. Datadog-canonical.

Datadog-specific tips

Datadog grades on whether you recognize the global-vs-local trap. The wrong approach (only checking immediate children) passes 80% of test cases — interviewers specifically use the [5,1,7,null,null,4,9] counterexample to catch this. Articulate the bounds-passing approach BEFORE coding.

Common mistakes

  • Only checking parent-child relationships, missing the global property.
  • Using Number.MIN_SAFE_INTEGER / MAX_SAFE_INTEGER without realizing nums can be 2^31-1 — use -Infinity / Infinity.
  • Using <= and >= incorrectly — BST is strict (no duplicates allowed in standard definition).

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

  • BST Iterator (LC 173) — yield in-order via explicit stack.
  • Recover BST (LC 99) — fix two swapped nodes.
  • Datadog-style: validate an ordered hierarchical metric tag tree.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why use bounds instead of in-order traversal?

In-order works (BST iff in-order is strictly ascending). Bounds-passing is more direct — no need to allocate the traversal output.

What about duplicates?

Standard definition disallows them. Some variants allow equality on one side; clarify with the interviewer.

Practice these live with InterviewChamp.AI

Drill Validate Binary Search Tree and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →