MediumDSAAsked in 20245 min read

Validate a Binary Search Tree

Q: Validate a Binary Search Tree

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Medium > **How to read this doc:** the classic mistake is checking only parent against child. This doc verified the failing tree directly (`[10,5,15,null,null,6,20]`: the naive check says valid, wrongly), then checked two correct approaches against an independent O(n²) oracle on 20,000 random trees with zero mismatches. The recursion limit was measured too. ## 1. The problem, restated A binary search tree requires that for EVERY node, all values in its left subtree are smaller and all values in its right subtree are larger (under a strict ordering here, so duplicates are invalid). It is a property of whole subtrees, not just of a node and its two children. ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | Duplicates? | Definitions differ. This solution uses strict ordering, so equal values are invalid; state whichever you choose. | |

1.6k views

74 of 154

The problem

Problem, as an interviewer would state it: "Given the root of a binary tree, determine whether it is a valid binary search tree. Discuss edge cases, runtime, and alternative approaches."

Examples:

Code

    2            5
   / \          / \
  1   3        1   4      <- 4 is smaller than 5: invalid
                  / \
                 3   6

Clarifying questions expected:

Are duplicate values allowed, and if so on which side?
Does the tree need to satisfy the ordering for the WHOLE left and right subtrees, not just the immediate children?
How deep can the tree be (recursion limits)?

Code / implementation expected: Yes — real, direct proof against an independent oracle, plus the tree that a naive check gets wrong.

js-coding
utility
algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Medium

How to read this doc: the classic mistake is checking only parent against child. This doc verified the failing tree directly ([10,5,15,null,null,6,20]: the naive check says valid, wrongly), then checked two correct approaches against an independent O(n²) oracle on 20,000 random trees with zero mismatches. The recursion limit was measured too.

1. The problem, restated

A binary search tree requires that for EVERY node, all values in its left subtree are smaller and all values in its right subtree are larger (under a strict ordering here, so duplicates are invalid). It is a property of whole subtrees, not just of a node and its two children.

2. Clarifying questions a strong candidate asks

Question	Why it matters
Duplicates?	Definitions diff

The solution is hidden so you can try first

5 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: bounds-based and in-order validators agree with an O(n^2) oracle on random trees, and a parent-child check is shown to accept an invalid tree

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 74 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextMedium→

Run Async Functions in Sequence, Each Using the Previous Result (Promise Waterfall)

Continue