What are Persistent Data Structures?

Learn how persistent data structures keep old versions queryable using path copying, with partial vs full persistence.

hardQ211 of 227 in Data Structures & Algorithms Est. time: 6 minsLast updated: July 2026

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

Persistent binary search tree via path copying

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 5

Follow-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?

2. What distinguishes full persistence from partial persistence?

3. What is the fat-node technique an alternative to?

Flash Cards

1 / 4

What are Persistent Data Structures?

Expected Interview Answer

AI Mentor Explanation

Step-by-Step Explanation

Choose a tree-based structure

Copy only the update path

Share untouched subtrees by reference

Keep a version root pointer per version