juniorTrees

What is a binary search tree and what are its operations?

Updated Feb 20, 2026

Short answer

A binary search tree keeps every node's left subtree strictly less than it and its right subtree greater, so an in-order traversal yields sorted output. Search, insert, and delete all follow one root-to-leaf path, which is O(log n) on a balanced tree. The catch is that nothing enforces balance — sorted insertions degenerate it into a linked list with O(n) operations.

Deep explanation

Python
class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None


def search(node, key):
    while node:
        if key == node.key: return node
        node = node.left if key < node.key else node.right
    return None


def insert(node, key):
    if node is None: return Node(key)
    if key < node.key:   node.left  = insert(node.left, key)
    elif key > node.key: node.right = insert(node.right, key)
    return node                        # equal keys ignored

Every operation is the same walk: compare, go left or right, repeat. Cost is the tree's height.

Deletion is the operation worth knowing properly, because it has three cases:

  • Leaf — remove it.
  • One child — splice the child into its place.
  • Two children — replace the key with its in-order successor (the leftmost node of the right subtree), then delete that successor, which by construction has at most one child.

Balance is the whole story. A balanced tree has height log n; a degenerate one has height n.

TypeScript
insert 1,2,3,4,5 in order:      insert 3,2,4,1,5:
  1                                   3
   \                                 /     2                               2   4
     \                             /           3   ...  height n           1       5    height log n

Inserting sorted data — extremely common, since data often arrives ordered — produces the worst case. This is exactly why self-balancing variants exist: AVL trees rebalance aggressively via rotations for faster lookups, red-black trees rebalance more loosely for faster insertion. Almost every "tree" in a standard library (std::map, Java's TreeMap) is a red-black tree, not a plain BST.

Against a hash table: a BST is slower for pure lookup, O(log n) against O(1), but supports ordered iteration, range queries, and nearest-neighbour searches that a hash table cannot answer at all.

Real-world example

A leaderboard needing both point lookups and range queries:

Python
def in_range(node, lo, hi, out):
    if not node: return
    if node.key > lo: in_range(node.left, lo, hi, out)      # prune
    if lo <= node.key <= hi: out.append(node.key)
    if node.key < hi: in_range(node.right, lo, hi, out)

Fetching every score between 1,000 and 2,000 visits only the relevant part of the tree — the node.key > lo and node.key < hi guards prune whole subtrees. A hash table would have to scan all n entries, because it stores no ordering at all.

Common mistakes

  • - Assuming O(log n) unconditionally
  • that holds only while balanced, and sorted insertion produces O(n).
  • - Mishandling the two-child deletion case — the replacement must be the in-order predecessor or successor, not an arbitrary child.
  • - Writing `<=` in the comparison and allowing duplicates on both sides, which breaks the search invariant.
  • - Checking only immediate children when validating a BST. Every node must sit within a range inherited from its ancestors, not merely be greater than its parent.
  • - Choosing a BST for pure key-value lookup where a hash table is faster and simpler
  • the BST earns its place only when ordering matters.

Follow-up questions

  • How do you verify a binary tree is a valid BST?
  • What is the difference between an AVL tree and a red-black tree?
  • Why does in-order traversal produce sorted output?
  • When would you choose a BST over a hash table?

More Trees interview questions

View all →