What are Persistent Data Structures?
Learn how persistent data structures keep old versions queryable using path copying, with partial vs full persistence.
Expected Interview Answer
A persistent data structure preserves every previous version of itself after an update, so old versions remain fully accessible and queryable, typically implemented via path copying or fat nodes so an update only touches O(log n) nodes instead of copying the whole structure.
In a partially persistent structure you can query any past version but only update the latest one, while a fully persistent structure lets you both query and branch updates off of any past version, forming a version tree rather than a single timeline. The standard implementation technique is path copying: for a balanced tree, an update creates new copies only of the nodes on the path from the root to the modified node, while all untouched subtrees are shared by reference with the old version, keeping each update to O(log n) extra space and time instead of O(n) for a full copy. An alternative, fat nodes, stores a small list of (version, value) pairs inside each node instead of duplicating nodes, trading simpler updates for slightly slower reads that must scan the version list. Persistent structures are essential for version-controlled systems, undo/redo history, functional programming immutable collections, and algorithms that need to query 'what did this structure look like at time t' efficiently.
- Old versions remain queryable after updates
- Path copying keeps each update to O(log n) extra space/time
- Enables safe concurrent reads of any historical version
- Backbone of functional immutable collections and undo/redo systems
AI Mentor Explanation
A cricket board keeps every past edition of the official team-selection tree instead of overwriting it whenever a player is swapped. Rather than photocopying the entire selection document each time, only the branch of the tree from the top-level squad down to the specific position that changed gets redrawn, while every untouched branch is simply referenced from the previous edition. This means selectors can pull up exactly how the squad looked before the third Test, browsing that old version freely, while the current squad keeps evolving independently. It is why a full selection history audit can compare any two points in time without ever needing a full separate copy stored for every single change.
Step-by-Step Explanation
Step 1
Choose a tree-based structure
Persistent structures are usually built on balanced trees (e.g. tries, balanced BSTs) rather than flat arrays, since trees allow sharing subtrees.
Step 2
Copy only the update path
On update, create new copies of the O(log n) nodes from the root to the modified leaf; leave all other subtrees untouched.
Step 3
Share untouched subtrees by reference
The new version’s unchanged branches point to the exact same nodes as the old version, avoiding a full copy.
Step 4
Keep a version root pointer per version
Each version is identified by its own root pointer, so any past version remains queryable by following its root.
What Interviewer Expects
- Distinguish partial from full persistence
- Explain path copying and why it costs O(log n) per update, not O(n)
- Contrast path copying with the fat-node technique
- Name real use cases: version control, undo/redo, functional immutable collections
Common Mistakes
- Confusing persistence with simple immutability of a single object
- Assuming persistent structures always cost O(n) per update, ignoring path copying
- Forgetting that array-based structures don’t share substructure as cheaply as trees
- Mixing up partial persistence (query-only past) with full persistence (branch from past)
Best Answer (HR Friendly)
“A persistent data structure keeps every old version alive after an update instead of overwriting it, so I can still query how it looked before. I would use path copying on a tree so each update only touches a small path of nodes instead of duplicating everything, which is exactly how undo history or version control systems work efficiently.”
Code Example
class Node:
__slots__ = ("key", "value", "left", "right")
def __init__(self, key, value, left=None, right=None):
self.key = key
self.value = value
self.left = left
self.right = right
def insert(root, key, value):
if root is None:
return Node(key, value)
if key < root.key:
return Node(root.key, root.value, insert(root.left, key, value), root.right)
elif key > root.key:
return Node(root.key, root.value, root.left, insert(root.right, key, value))
else:
return Node(key, value, root.left, root.right)
def find(root, key):
node = root
while node is not None:
if key == node.key:
return node.value
node = node.left if key < node.key else node.right
return None
# Each insert returns a NEW root; old roots stay valid and queryable.
v0 = None
v1 = insert(v0, 5, "a")
v2 = insert(v1, 3, "b")
v3 = insert(v2, 5, "z") # updates key 5, but v2 still has value “a” at key 5Follow-up Questions
- How does the fat-node technique differ from path copying in terms of read cost?
- How would you implement a persistent array with O(log n) reads and writes?
- How do persistent data structures relate to Git’s object model?
- How would you garbage-collect old versions in a fully persistent structure?
MCQ Practice
1. What is the extra space/time cost of one update using path copying on a balanced tree of n nodes?
Only the nodes on the root-to-modified-node path are copied; all other subtrees are shared by reference, giving O(log n) per update.
2. What distinguishes full persistence from partial persistence?
Partial persistence allows querying old versions but only updating the newest; full persistence allows branching new updates from any past version too.
3. What is the fat-node technique an alternative to?
Fat nodes store multiple (version, value) pairs per node instead of copying nodes along the update path, trading write simplicity for slower reads.
Flash Cards
What does a persistent data structure guarantee? — Every previous version remains fully accessible and queryable after an update.
What technique keeps updates to O(log n) on a persistent tree? — Path copying: only nodes from root to the modified node are duplicated; other subtrees are shared.
What is the difference between partial and full persistence? — Partial allows querying old versions but updates only the latest; full allows branching updates from any past version.
Name a real-world use of persistent data structures. — Version control systems, undo/redo history, and immutable collections in functional programming.