Course contentsShow
← Computer Science
Lesson 525 of 2,87212. Binary Search TreesFree lesson

Space Complexity of BSTs

Understanding memory requirements for BST storage including node overhead and pointer space.

Space Complexity of BSTs

What you'll learn: You'll understand how much memory a Binary Search Tree actually consumes, including the overhead beyond just storing your data.


Understanding Memory Requirements

When you store data in a BST, you're not just storing the values themselves—you're also storing the structure that makes the tree work. Every node needs memory for:

  1. The data value (e.g., an integer, string, or object reference)
  2. Two pointers (left and right child references)
  3. Optional metadata (parent pointer, balance factors, color bits for self-balancing variants)

Think of it like storing books in boxes: you need space for the books themselves plus the boxes, labels, and shelving that organize them.

The Space Complexity Formula

For a BST with n nodes:

Space = O(n)

This is linear space complexity. Each node requires constant space O(1), and you have n nodes total. However, the constant factor matters in practice:

  • Minimum per node: data + 2 pointers (typically 12-24 bytes for simple integer keys)
  • With parent pointers: add another 4-8 bytes per node
  • Pointer overhead: Often 50-75% of total memory goes to structural pointers rather than data

Hidden Memory Costs

Don't forget implicit space from recursion! When you perform recursive operations (insertion, search, deletion), the call stack uses O(h) memory, where h is the tree height:

  • Best case (balanced): O(log n) stack space
  • Worst case (skewed): O(n) stack space

Key Takeaway: BSTs use O(n) space where n is the number of nodes, but significant memory overhead comes from storing pointers (not just data), and recursive operations add O(h) implicit stack space proportional to tree height.