Interview Cake
A binary search tree with nodes containing integers. The root node contains the integer 50. Each child node to the left of the root contains integers less than 50, and each child node to the right of the root contains integers greater than 50.

Binary Search Tree

Data Structure

Costs

Balanced Unbalanced (Worst Case)
space
insert
lookup
delete

Quick reference

A binary search tree is a binary tree where the nodes are ordered in a specific way. For every node:

  • The nodes to the left are smaller than the current node.
  • The nodes to the right are larger than the current node.

Checking if a binary tree is a binary search tree is a favorite question from interviews.

A binary search tree with nodes containing integers. The root node contains the integer 50. Each child node to the left of the root contains integers less than 50, and each child node to the right of the root contains integers greater than 50.

Strengths:

  • Good performance across the board. Assuming they're balanced, binary search trees are good at lots of operations, even if they're not constant time for anything.

    • Compared to a sorted array, lookups take the same amount of time (), but inserts and deletes are faster ( for BSTs, for arrays).
    • Compared to hash maps, BSTs have better worst case performance— instead of . But, on average hash maps perform better than BSTs (meaning time complexity).
  • BSTs are sorted. Taking a binary search tree and pulling out all of the elements in sorted order can be done in using an in-order traversal. Finding the element closest to a value can be done in (again, if the BST is balanced!).

Weaknesses:

  • Poor performance if unbalanced. Some types of binary search trees balance automatically, but not all. If a BST is not balanced, then operations become .
  • No operations. BSTs aren't the fastest for anything. On average, an array or a hash map will be faster.

Balanced Binary Search Trees

Two binary search trees can store the same values in different ways:

Two binary search trees: the one on the left is balanced and the one on the right is unbalanced. Both contain the same values: the integers 1 through 6.

Some trees (like AVL trees or Red-Black trees) rearrange nodes as they're inserted to ensure the tree is always balanced. With these, the worst case complexity for searching, inserting, or deleting is always , not .

See also:

. . .