Solving Validate Binary Search Tree in JavaScript: Step-by-Step Guide

Introduction to Validate Binary Search Tree

The "Validate Binary Search Tree" problem is one of the most classic algorithmic challenges you'll encounter in technical interviews and on platforms like LeetCode. At its core, the problem asks a deceptively simple question: given the root of a binary tree, determine whether it is a valid Binary Search Tree (BST).

A Binary Search Tree is a tree data structure where every node follows a strict ordering rule. For each node, all values in its left subtree must be strictly less than the node's value, and all values in its right subtree must be strictly greater than the node's value. Both subtrees must themselves also be valid BSTs. This ordering property is what makes BSTs so powerful for searching, inserting, and deleting values in logarithmic time.

Why This Problem Matters

Understanding how to validate a BST is foundational for several reasons. First, it forces you to deeply understand tree traversal techniques, particularly depth-first search. Second, it teaches you how to propagate constraints down a recursive call stack — a pattern that appears in countless other tree and graph problems. Finally, BSTs underpin many real-world systems, including database indexes, in-memory ordered maps, and range query structures. If a BST is malformed, every operation that depends on its ordering property can silently produce incorrect results.

Understanding the Problem Statement

Before writing any code, let's precisely define the problem. You are given a root node of a binary tree. Each node has three properties: val, left, and right. You must return true if the tree is a valid BST and false otherwise.

The key constraints to remember are:

• The left subtree of a node contains only nodes with values less than the node's value.
• The right subtree of a node contains only nodes with values greater than the node's value.
• Both left and right subtrees must also be valid BSTs.
• Duplicate values are not allowed in a valid BST (the comparison is strict).

A common mistake is to only check that the immediate left child is smaller and the immediate right child is larger. This is insufficient because a deeply nested node could violate the constraint imposed by an ancestor higher up the tree.

Defining the Tree Node

Let's start by defining the tree node structure we'll use throughout this tutorial.

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

This simple class represents a single node in our binary tree. We'll use it to construct test cases and validate our solutions.

Solution 1: Recursive Approach with Min and Max Bounds

The most elegant solution uses recursion with a helper function that tracks the valid range for each node. As we traverse down the tree, we narrow the acceptable range. The root can be any value, but when we move left, the maximum allowed value becomes the current node's value. When we move right, the minimum allowed value becomes the current node's value.

How the Bounds Work

Imagine you're at a node with value 10. Any node in its left subtree must be less than 10. If you then move to the left child with value 5, any node in its right subtree must be greater than 5 but still less than 10. This is why we need to carry both a lower and upper bound as we recurse.

function isValidBST(root) {
  function validate(node, min, max) {
    // An empty node is a valid BST
    if (node === null) {
      return true;
    }

    // The current node's value must fall within the allowed range
    if ((min !== null && node.val <= min) || (max !== null && node.val >= max)) {
      return false;
    }

    // Recursively validate the left and right subtrees with updated bounds
    return (
      validate(node.left, min, node.val) &&
      validate(node.right, node.val, max)
    );
  }

  return validate(root, null, null);
}

Notice that we use null to represent an unbounded limit. This handles the case where node values might be at the edge of JavaScript's number range, such as Number.MIN_SAFE_INTEGER or Number.MAX_SAFE_INTEGER. Using null instead of hardcoded extremes avoids false negatives.

Tracing Through an Example

Let's trace through a concrete example to build intuition. Consider the following tree:

const tree = new TreeNode(
  5,
  new TreeNode(1),
  new TreeNode(7, new TreeNode(6), new TreeNode(8))
);

The validation proceeds as follows:

• Call validate(5, null, null). The value 5 is within bounds.
• Recurse left with validate(1, null, 5). The value 1 is less than 5 and has no lower bound. Valid.
• Node 1 has no children, so both return true.
• Recurse right with validate(7, 5, null). The value 7 is greater than 5. Valid.
• Recurse into 7's left child with validate(6, 5, 7). The value 6 is between 5 and 7. Valid.
• Recurse into 7's right child with validate(8, 7, null). The value 8 is greater than 7. Valid.
• All checks pass, so the function returns true.

Solution 2: In-Order Traversal Approach

An alternative and equally valid approach leverages a fundamental property of BSTs: an in-order traversal of a valid BST produces values in strictly ascending order. If we traverse the tree in-order (left, root, right) and verify that each value is greater than the previous one, we can confirm validity.

Iterative In-Order Traversal

Here's an iterative implementation using an explicit stack:

function isValidBST(root) {
  const stack = [];
  let current = root;
  let prev = null;

  while (stack.length > 0 || current !== null) {
    // Go as far left as possible
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    // Process the next node in-order
    current = stack.pop();

    // The current value must be greater than the previous value
    if (prev !== null && current.val <= prev.val) {
      return false;
    }

    prev = current;
    current = current.right;
  }

  return true;
}

This approach is particularly useful when you want to avoid recursion, perhaps due to stack overflow concerns with very deep trees. It also reads naturally: we're simply checking that the in-order sequence is strictly increasing.

Recursive In-Order Traversal

If you prefer a recursive style, the same logic can be expressed more concisely:

function isValidBST(root) {
  let prev = null;

  function inOrder(node) {
    if (node === null) {
      return true;
    }

    // Traverse left subtree first
    if (!inOrder(node.left)) {
      return false;
    }

    // Check current node against previous value
    if (prev !== null && node.val <= prev.val) {
      return false;
    }

    prev = node;

    // Traverse right subtree
    return inOrder(node.right);
  }

  return inOrder(root);
}

The prev variable is captured in the closure and persists across recursive calls, allowing us to compare each node against its in-order predecessor.

Comparing the Two Approaches

Both approaches have the same time and space complexity, but they differ in subtle ways that might influence your choice.

Time and Space Complexity

Both solutions run in O(n) time, where n is the number of nodes in the tree, because each node is visited exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack or explicit stack. In the worst case of a completely unbalanced tree, this becomes O(n). In a balanced tree, it's O(log n).

When to Use Each

The bounds-based recursive approach is generally preferred in interviews because it directly encodes the BST definition. It's also easier to extend — for example, if you later need to find the maximum valid subtree or repair an invalid BST, the bounds pattern adapts naturally.

The in-order traversal approach is more intuitive if you already understand the sorted-order property of BSTs. It's also a great choice when you need to perform additional operations during traversal, such as finding the kth smallest element or detecting the exact nodes that violate the BST property.

Common Pitfalls and How to Avoid Them

Only Checking Immediate Children

The most frequent mistake is checking only that node.left.val < node.val and node.right.val > node.val. This fails for trees like the following:

// Invalid BST, but naive check would pass
const badTree = new TreeNode(
  5,
  new TreeNode(1),
  new TreeNode(6, new TreeNode(3), new TreeNode(7))
);

Here, node 3 is in the right subtree of 5, but 3 is less than 5. A naive check only verifies that 6 is greater than 5, missing the violation deeper in the tree. The bounds-based approach catches this because when we recurse into node 6's left child, the lower bound is 5, and 3 fails that check.

Using Incorrect Initial Bounds

Another common error is initializing bounds with Number.MIN_VALUE and Number.MAX_VALUE. In JavaScript, Number.MIN_VALUE is the smallest positive number, not the most negative number. The correct extreme would be -Infinity and Infinity, but using null is cleaner and avoids any edge cases entirely.

Forgetting Strict Inequality

BSTs require strict inequality. Using <= or >= instead of < and > will incorrectly accept trees with duplicate values. Always double-check your comparison operators.

Best Practices

• Always clarify the BST definition with your interviewer. Some variations allow duplicates on one side. Confirm whether the comparison is strict before coding.
• Handle edge cases explicitly. An empty tree (null root) and a single-node tree are both valid BSTs. Make sure your solution returns true for both.
• Test with negative numbers and extreme values. Your bounds logic should handle values like -Infinity and large integers without breaking.
• Prefer the bounds approach for clarity. It maps directly to the BST definition and is easier to explain and debug.
• Consider iterative solutions for production code. Deeply nested trees can cause stack overflow with recursion. An iterative approach using an explicit stack gives you more control.
• Write helper functions with clear signatures. Naming parameters min and max (or low and high) makes the code self-documenting.

Testing Your Solution

A robust test suite is essential. Here are the key cases you should cover:

// Test 1: Valid BST
const validBST = new TreeNode(
  5,
  new TreeNode(3, new TreeNode(1), new TreeNode(4)),
  new TreeNode(8, new TreeNode(7), new TreeNode(9))
);
console.log(isValidBST(validBST)); // true

// Test 2: Invalid BST (right subtree contains smaller value)
const invalidBST = new TreeNode(
  5,
  new TreeNode(1),
  new TreeNode(6, new TreeNode(3), new TreeNode(7))
);
console.log(isValidBST(invalidBST)); // false

// Test 3: Empty tree
console.log(isValidBST(null)); // true

// Test 4: Single node
console.log(isValidBST(new TreeNode(1))); // true

// Test 5: Duplicate values
const duplicateTree = new TreeNode(
  2,
  new TreeNode(2),
  null
);
console.log(isValidBST(duplicateTree)); // false

// Test 6: Left subtree contains larger value
const leftViolation = new TreeNode(
  10,
  new TreeNode(5, null, new TreeNode(15)),
  new TreeNode(20)
);
console.log(isValidBST(leftViolation)); // false

Running these tests against both the bounds-based and in-order traversal implementations should produce identical results, giving you confidence that your solution is correct.

Conclusion

Validating a Binary Search Tree is a problem that beautifully illustrates the power of recursive thinking and the importance of carrying context through a traversal. Whether you choose the bounds-based approach or the in-order traversal method, the key insight is that local checks are not enough — you must propagate constraints from ancestors down to descendants. By understanding both solutions, their trade-offs, and the common pitfalls, you'll be well-equipped to tackle this problem in interviews and to apply the same patterns to more complex tree and graph challenges. Practice implementing both versions from memory, test them against edge cases, and you'll have mastered one of the most fundamental algorithms in computer science.