Interview Cake by Exponent
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

In short: A binary search tree (BST) is a binary tree where every node's left subtree holds smaller values and its right subtree holds larger ones. That ordering makes search, insertion, and deletion O(log n) on average, though O(n) if the tree becomes unbalanced.

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 dictionaries, BSTs have better worst case performance— instead of . But, on average dictionaries 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, a list or a dictionary 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:

Frequently Asked Questions

What is a binary search tree?

A binary tree with an ordering rule: for every node, all values in its left subtree are smaller and all values in its right subtree are larger.

What is the time complexity of a binary search tree?

O(log n) on average for search, insert, and delete, but O(n) in the worst case when the tree degenerates into a list. Self-balancing BSTs guarantee O(log n).

What's the difference between a binary tree and a binary search tree?

A binary tree just limits each node to two children; a BST adds the ordering rule that keeps left descendants smaller and right descendants larger than each node.

Last updated: June 17, 2026

. . .