What is a binary search tree (BST)? | Interview Question

Q: What is a binary search tree (BST)?

**Target Audience:** Beginners preparing for coding interviews — you only need to know what a variable, a loop and a function are. **Difficulty:** Easy **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 Play a guessing game with a friend: they think of a number between 1 and 100, you guess, and they only ever say "higher" or "lower". A smart player never guesses 1, 2, 3...; they guess 50, then 25 or 75, and so on, throwing away half of the remaining numbers with each question. Seven questions are always enough. Now imagine the numbers are not fixed — your friend keeps adding new

The problem

Question presented to candidate: "Explain what a binary search tree is. Then, in Python, show me how search, insert and delete work, and tell me what their running time depends on."

What a strong answer should cover:

The BST property: every key in a node's left subtree is smaller, every key in its right subtree is larger — for the whole subtree, not just the children.
Search, insert and delete each walk one root-to-leaf path, so they cost O(h), where h is the height.
The three delete cases (leaf, one child, two children) and the in-order successor.
In-order traversal visits the keys in sorted order.
Height is the whole story: about log2(n) when balanced, n − 1 when keys arrive sorted; self-balancing trees (AVL, red-black) keep it O(log n).
Python specifics: there is no BST in the standard library (dict is a hash table, bisect works on a sorted list), and a recursive insert on sorted keys hits the default recursion limit of 1000.

Code / implementation expected: Optional — a small Node class with insert, search and delete 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 only need to know what a variable, a loop and a function are.
Difficulty: Easy
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

Play a guessing game with a friend: they think of a number between 1 and 100, you guess, and they only ever say "higher" or "lower". A smart player never guesses 1, 2, 3...; they guess 50, then 25 or 75, and so on, throwing away half of the remaining numbers with each question. Seve

The solution is hidden so you can try first

15 min read · 12 sections

Python code

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

PythonBST basics: insert, search, delete (3 cases), in-order

Practice

PythonShape experiment: sorted vs shuffled vs balanced (1,023 keys)

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.