DSA interview question

Validate a Binary Search Tree

Medium · Algorithms · Topics: bst, recursion

The problem

A data-integrity job receives binary trees claimed to be BSTs and must verify them before they're used for lookups. Checking only that each node is greater than its left child and less than its right child isn't enough: a node deep in the right subtree must also exceed every ancestor it sits to the right of. The robust check passes down an allowed range (low, high). Going left tightens the upper bound to the parent's value, going right tightens the lower bound, and every node must fall strictly inside its range.

Example: [5, 1, 4, null, null, 3, 6] → false (4 is in 5's right subtree but smaller than 5).

Function signature

bool isValidBST(TreeNode* root);  // strict: no duplicates allowed

Test cases

Input (level order)	Output	Explanation
`[2, 1, 3]`	`true`
`[5, 1, 4, null, null, 3, 6]`	`false`	4 < 5 in the right subtree
`[5, 4, 6, null, null, 3, 7]`	`false`	3 is below 6 but also below 5
`[2, 2, 2]`	`false`	Equal keys aren't allowed
`[2147483647]`	`true`	INT_MAX as a key
`[-2147483648, null, 2147483647]`	`true`	Extremes need 64-bit bounds

(Confirm: strict ordering, meaning left < node < right for all descendants; keys can be any 32-bit value.)

How interviewers phrase it

"Given the root of a binary tree, determine if it is a valid binary search tree" (LeetCode 98).

Clarifying questions to ask

Are duplicates allowed? (No: strict inequality.)
What's the key range? (The full 32-bit range, so the sentinels must be wider.)
Is an empty tree valid? (Yes.)

Follow-ups to expect

"Why isn't the local parent–child check enough?"
"How do bounds fix it?"
"Why use long long or pointers for the bounds?"
"Inorder alternative?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview