Pattern Studioalgorithmic thinking
All patterns

Binary Search Trees

Trees
Intermediate
Interactive

Choose left or right using the ordering invariant.

Time
O(h), O(log n) balanced
Space
O(1) iterative
ActiveComparingMatch / bestIn windowFrontierVisitedExcludedAnswer
No frames to display.

The idea

A BST keeps smaller values in the left subtree and larger values in the right subtree. Search uses that invariant to discard an entire subtree after every comparison.

Analogy

A reusable way to think about organizing and navigating structured data efficiently.

When to reach for it

  • The relationships between values drive the algorithm.
  • You need efficient traversal, lookup, or updates.
  • An interview problem names or implies this structure.

Language-independent template

node = root
while node and node.value != target:
    node = node.left if target < node.value else node.right

Complexity — time O(h), O(log n) balanced, space O(1) iterative.

Common mistakes

  • Losing a pointer before saving its next target.
  • Breaking the structure invariant during an update.
  • Forgetting empty and single-node cases.

Practice progression

Canonical interview problems, ordered from foundation to advanced application.

Easy
Search in a Binary Search TreeLC 700

Find and return the node containing a target value.

Medium
Kth Smallest Element in a BSTLC 230

Return the kth value in sorted BST order.

Hard
Maximum Sum BST in Binary TreeLC 1373

Find the maximum node sum among all BST subtrees.

Variations

Traversal
Insertion and deletion
Search and reconstruction