Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree with an additional ordering property:

For every node x, all keys in x.left are less than x.key,
and all keys in x.right are greater than x.key.

This property lets BSTs support search and updates in O(h) time, where h is the tree height.

Core Operations

Assuming distinct keys, the main operations are:

  • Search:
    • Compare target with current node’s key:
      • If equal, done.
      • If smaller, go left.
      • If larger, go right.
  • Insert:
    • Search for the position a new key would occupy and attach a new node there.
  • Delete:
    • More nuanced; three cases:
      1. Node is a leaf → just remove it.
      2. Node has one child → replace node with its child.
      3. Node has two children → replace its key with its inorder successor (smallest in right subtree) or predecessor, then delete that successor/predecessor node.

All of these are O(h) where h is the height of the tree.

Inorder Traversal and Sorted Order

In a BST, inorder traversal (left, node, right) visits nodes in sorted order of keys.

This is a powerful property:

  • Generate sorted list from BST in O(n).
  • Check if a binary tree is a valid BST by verifying that inorder traversal is strictly increasing.

Balanced vs Unbalanced BSTs

In the best case (balanced BST):

  • Height h is O(log n).
  • Search / insert / delete are O(log n).

In the worst case (degenerate BST, e.g. inserting sorted values into a naive BST):

  • Height h becomes O(n).
  • Operations degrade to O(n) like a linked list.

Balanced BST variants (AVL, Red‑Black, etc.) maintain near‑balanced height via rotations after inserts and deletes, guaranteeing O(log n) operations.

BSTs in Interviews

You’ll often see:

  • Finding floor/ceil or predecessor/successor of a key.
  • Validating whether a binary tree is a BST.
  • Range queries (e.g. count keys in [L, R]).
  • Converting a sorted array to a balanced BST (divide & conquer).

Key patterns:

  • Use the BST property to prune recursion:
    • If target < root.key, ignore right subtree.
    • If target > root.key, ignore left subtree.
  • Use inorder traversal when you need sorted sequences or relative ordering.

When to Use a BST

BSTs are a good fit when:

  • You need both ordering and logarithmic search/insert/delete.
  • You want to support range queries (e.g. “all keys between L and R”).

In many practical systems, specialized balanced BSTs (e.g. B‑trees) or skip lists are used for indexes, but the BST abstraction is the conceptual starting point.