Skip to main content

20. Validate Binary Search Tree

mediumAsked at Freshworks

Verify a binary tree satisfies the BST property — Freshworks asks this when probing whether you can reason about a permission tree's ordering invariant.

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

Problem

Given the root of a binary tree, determine if it is a valid binary search tree. A valid BST has every node's left subtree containing values strictly less than the node and right subtree strictly greater.

Constraints

  • 1 <= number of nodes <= 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

Approaches

1. Brute force (compare only direct children)

Recurse and check left.val < node.val < right.val. Wrong — it misses cross-subtree violations like [10,5,15,null,null,6,20].

Time
O(n)
Space
O(h)
function bad(node){ if(!node) return true; if(node.left && node.left.val >= node.val) return false; if(node.right && node.right.val <= node.val) return false; return bad(node.left) && bad(node.right); }

Tradeoff:

2. DFS with running min/max bounds

Pass down the allowed open interval (low, high). Each node must satisfy low < val < high. Recurse with tightened bounds on each side.

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

Tradeoff:

Freshworks-specific tips

Freshworks loves to trap candidates with the [5,1,4,null,null,3,6] case — name that exact gotcha before coding so they see you anticipated the cross-subtree bug.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →