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:
- The data value (e.g., an integer, string, or object reference)
- Two pointers (left and right child references)
- 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.