What is a Binary Search Tree (BST)?
Learn what a binary search tree is — the ordering property, O(log n) operations, in-order traversal and balancing — with examples and DSA interview questions.
Expected Interview Answer
A binary search tree is a binary tree where every node’s left subtree holds smaller keys and its right subtree holds larger keys, enabling search, insertion, and deletion in O(log n) time when the tree is balanced.
Because of the ordering property, searching mirrors binary search: compare with the current node and go left or right, halving the search space each step. An in-order traversal visits keys in sorted order. The catch is balance — inserting sorted data produces a skewed tree that degrades to O(n), which is why self-balancing variants (AVL, Red-Black) exist to keep the height logarithmic.
- O(log n) search/insert/delete when balanced
- In-order traversal yields sorted output
- Supports range queries and ordered iteration
AI Mentor Explanation
A BST is like organizing players by strike rate in a decision tree: at each node you ask "higher or lower?" and branch left for lower, right for higher, halving the candidates each step until you find your player. In-order walking the tree lists everyone in strike-rate order. But if you insert players already sorted, the tree becomes a long chain and the fast halving is lost — exactly why balanced BSTs exist.
Step-by-Step Explanation
Step 1
Ordering property
Left subtree < node < right subtree, recursively, for every node.
Step 2
Search
Compare and go left/right — O(log n) when balanced.
Step 3
In-order traversal
Left, node, right visits keys in ascending sorted order.
Step 4
Balance matters
Skewed trees degrade to O(n); AVL/Red-Black keep height logarithmic.
What Interviewer Expects
- The left < node < right ordering property
- Logarithmic operations only when balanced
- In-order traversal producing sorted output
- Awareness of self-balancing trees (AVL, Red-Black)
Common Mistakes
- Claiming BSTs are always O(log n) regardless of shape
- Confusing a BST with any binary tree
- Forgetting the worst-case O(n) skewed tree
- Not knowing in-order traversal yields sorted order
Best Answer (HR Friendly)
“A binary search tree keeps data ordered — smaller values on the left, larger on the right — so you can find, add, or remove items quickly by halving the search each step. It stays fast only when balanced, which is why balanced versions like AVL and Red-Black trees exist.”
Code Example
class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None
def search(node, target):
while node:
if target == node.key:
return node
node = node.left if target < node.key else node.right
return None # O(log n) when the tree is balancedFollow-up Questions
- What is the worst-case time complexity of a BST and when does it occur?
- How do AVL and Red-Black trees keep a BST balanced?
- How do you delete a node with two children?
- Why does in-order traversal produce sorted output?
MCQ Practice
1. In a BST, the left subtree of a node contains keys that are?
By the BST property, all left-subtree keys are smaller than the node’s key.
2. Which traversal of a BST yields sorted order?
In-order (left, node, right) visits keys in ascending order.
3. A BST built by inserting already-sorted data degrades to?
Sorted insertion creates a skewed chain, giving linear-time operations.
Flash Cards
BST ordering property? — Left subtree < node < right subtree, for every node.
Balanced BST operations? — Search, insert, delete in O(log n).
In-order traversal gives? — Keys in ascending sorted order.
Worst case and fix? — Skewed tree → O(n); fixed by AVL/Red-Black balancing.