How do you validate that a binary tree is a BST? | Interview Question

Q: How do you validate that a binary tree is a BST?

**Target Audience:** Beginners preparing for coding interviews — you should know what a binary tree and recursion are. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First A library shelves its books by number. Each shelf has a sign: "everything to the left of me is smaller, everything to the right is bigger". A new assistant checks the shelves by looking at each sign and the two books right next to it. Every check passes — and yet a reader still cannot find book 3, because someone put it three shelves to the right of book 5, next to book 6. Book 3 is smaller

The problem

Question presented to candidate: "You are given the root of a binary tree. Write a Python function that returns true if it is a valid binary search tree — every key in a node's left subtree is strictly smaller than the node, and every key in its right subtree is strictly larger."

What a strong answer should cover:

Why comparing each node only with its two children is wrong (a deep descendant can break the rule), with a counter-example.
The range method: pass down an open interval (low, high) that tightens at every step; O(n) time, O(h) space.
The in-order method: an in-order walk of a BST is strictly increasing, so compare each value with the previous one and stop at the first drop.
Duplicates: with the strict definition, equal keys make the tree invalid.
Python specifics: use None (or float('-inf') / float('inf')) for "no bound", and prefer the iterative in-order version on deep trees because recursion stops at about 1000 frames by default.

Clarifying questions expected:

Are duplicate values allowed, and if so on which side?
How deep can the tree be (is recursion safe)?

Code / implementation expected: Yes — a recursive range check or an iterative in-order check with a list as the stack, in Python 3.

trees
bst

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: Beginners preparing for coding interviews — you should know what a binary tree and recursion are.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

A library shelves its books by number. Each shelf has a sign: "everything to the left of me is smaller, everything to the right is bigger". A new assistant checks the shelves by looking at each sign and the two books right next to it. Every check passes — and yet a reader still cannot find bo

The solution is hidden so you can try first

7 min read · 12 sections

Python code

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

PythonLocal check vs range check vs in-order check (7 trees)

Practice

PythonSentinel-bound bug, and early exit on a 5,000-node chain

Practice

Discussion

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

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.