Skip to main content

DSAPath9 mincore

Binary Search Trees

A binary search tree stores keys so every left-subtree key is smaller and every right-subtree key is larger. Balanced BSTs support ordered lookup, predecessor, successor, and range queries in logarithmic time.

Why This Matters

Hash tables give lookup but lose order. BSTs keep order: they can find minimum, maximum, predecessor, successor, and all keys in a range.

Core Idea

For every node with key kk, all keys in the left subtree are below kk, and all keys in the right subtree are above kk.

OperationBalanced BSTUnbalanced BST
searchO(log⁡n)O(\log n)O(n)O(n)
insertO(log⁡n)O(\log n)O(n)O(n)
deleteO(log⁡n)O(\log n)O(n)O(n)
range queryO(log⁡n+m)O(\log n + m)O(n+m)O(n + m)

Worked example: inorder traversal of a BST lists keys in sorted order.

Common Mistakes

  • Saying BST operations are always O(log⁡n)O(\log n). That requires a height guarantee.
  • Forgetting duplicate-key policy. The tree must define where equal keys go.
  • Using a BST where a hash table is simpler and order is not needed.

Exercises

  • Insert 5, 2, 8, 1, 3 into a BST and draw it.
  • Explain why sorted insertion creates a chain.
  • State one reason a tree map can beat a hash map.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 12, 13.
  • Sedgewick and Wayne. Algorithms (4th ed., 2011). Ch. 3.