What is a Zipper?

A Zipper is a functional data structure used to represent a cursor or pointer focused on a specific subcomponent of a data structure (such as a tree or list). It stores:

Focus: The subtree currently being inspected or modified.

Context (Breadcrumbs): The path taken from the root to the focus, allowing you to reconstruct the parents and siblings in $O (1)$ time.

Explanation

In functional programming, data structures are immutable. If you want to modify a leaf node in a large binary tree, you cannot just overwrite its value; you must duplicate and rebuild all the parent nodes up to the root. A Zipper turns the data structure “inside out” around the node of interest (the focus), allowing local traversals and edits to run in $O (1)$ time.

Real-World Analogy

Zip-Line Trolley with Breadcrumbs: Imagine traversing a dense forest canopy using a zip-line harness. The trolley holds you at your current tree branch (the focus). Behind you, a string of markers (breadcrumbs) records every left or right turn you took from the forest entry point. If you want to change a branch or climb back up to the entrance, you only have to look at the immediate string of markers, avoiding search operations.

How It Works

Core Mechanics

Let’s represent a Binary Tree Zipper.

1. Tree Node Structure

A normal binary tree node: Node(value, left, right).

A breadcrumb tracks a single step up the tree. It stores:
- direction: Whether we traversed Left or Right to reach the current child.
- value: The value of the parent node.
- sibling: The sibling subtree that was not traversed (e.g. if we went left, the right child).

3. Zipper Operations

go_left():
- Move the focus to the current node’s left child.
- Push a new breadcrumb onto the stack containing (Direction.LEFT, parent_value, right_sibling).
go_right():
- Move the focus to the current node’s right child.
- Push a new breadcrumb onto the stack containing (Direction.RIGHT, parent_value, left_sibling).
go_up():
- Pop a breadcrumb from the stack.
- Reconstruct the parent node using the popped value, sibling, direction, and current focused node.
- Focus on the reconstructed parent.
update(new_value):
- Replaces the current focused node with a new node containing new_value. Takes $O (1)$ time.

Visual Walkthrough

Tree structure: Root (1) with left (2) and right (3)

    1
   / \
  2   3

Zipper initialized at Root (1)

Focus: Node(1, Node(2), Node(3))
Breadcrumbs: [] (Empty)

Move Left (`go_left()`)

We transition focus to 2. The parent value 1 and sibling 3 are saved as context:
Focus: Node(2)
Breadcrumbs: [LeftStep(parent_val=1, sibling=Node(3))]

Update node value to 99 (`update(99)`)

Update the local focus without rebuilding the root yet:
Focus: Node(99)
Breadcrumbs: [LeftStep(parent_val=1, sibling=Node(3))]

Move Up (`go_up()`)

Rebuild the parent node. Since the breadcrumb direction was Left, the updated node 99 becomes the parent’s new left child:
Focus: Node(1, Node(99), Node(3))
Breadcrumbs: []

Time & Space Complexity

Operation	Standard Immutable Tree (No Zipper)	Binary Tree Zipper
Move Left/Right	$O (lo g N)$ (rebuild path)	$O (1)$
Move Up	$O (lo g N)$	$O (1)$
Modify focused node	$O (lo g N)$	$O (1)$
Reconstruct Root	-	$O (depth)$
Space Complexity	$O (1)$ auxiliary	$O (depth)$ (for breadcrumbs)

Implementation

from enum import Enum
 
class Direction(Enum):
    LEFT = 1
    RIGHT = 2
 
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
 
    def __repr__(self):
        return f"Node({self.value}, {self.left}, {self.right})"
 
class Breadcrumb:
    def __init__(self, direction, parent_value, sibling):
        self.direction = direction
        self.parent_value = parent_value
        self.sibling = sibling # The subtree we did not enter
 
class TreeZipper:
    def __init__(self, node, breadcrumbs=None):
        self.focus = node
        self.breadcrumbs = breadcrumbs if breadcrumbs else []
 
    def go_left(self):
        """Focuses on the left child, saving the right child as context."""
        if not self.focus or not self.focus.left:
            raise ValueError("Cannot move left: Left child does not exist")
        
        # Save context
        step = Breadcrumb(Direction.LEFT, self.focus.value, self.focus.right)
        new_breadcrumbs = self.breadcrumbs + [step]
        return TreeZipper(self.focus.left, new_breadcrumbs)
 
    def go_right(self):
        """Focuses on the right child, saving the left child as context."""
        if not self.focus or not self.focus.right:
            raise ValueError("Cannot move right: Right child does not exist")
        
        # Save context
        step = Breadcrumb(Direction.RIGHT, self.focus.value, self.focus.left)
        new_breadcrumbs = self.breadcrumbs + [step]
        return TreeZipper(self.focus.right, new_breadcrumbs)
 
    def go_up(self):
        """Reconstructs the parent node and moves focus up."""
        if not self.breadcrumbs:
            raise ValueError("Cannot move up: Already at the root")
        
        last_step = self.breadcrumbs[-1]
        parent_val = last_step.parent_value
        sibling = last_step.sibling
        
        # Rebuild node
        if last_step.direction == Direction.LEFT:
            parent_node = TreeNode(parent_val, self.focus, sibling)
        else:
            parent_node = TreeNode(parent_val, sibling, self.focus)
            
        return TreeZipper(parent_node, self.breadcrumbs[:-1])
 
    def update(self, new_value):
        """Replaces the value of the focused node."""
        if not self.focus:
            new_focus = TreeNode(new_value)
        else:
            new_focus = TreeNode(new_value, self.focus.left, self.focus.right)
        return TreeZipper(new_focus, self.breadcrumbs)
 
    def to_root(self):
        """Ascends all the way to the root and returns the reconstructed tree."""
        zipper = self
        while zipper.breadcrumbs:
            zipper = zipper.go_up()
        return zipper.focus
 
# Example Usage
if __name__ == "__main__":
    # Build tree: Node(1, Node(2), Node(3))
    root = TreeNode(1, TreeNode(2), TreeNode(3))
    zipper = TreeZipper(root)
    
    # Traverse Left to node 2, update to 99, and reconstruct root
    zipper = zipper.go_left()
    zipper = zipper.update(99)
    new_root = zipper.to_root()
    print("Updated Tree:", new_root) # Node(1, Node(99, None, None), Node(3, None, None))

#include <iostream>
#include <vector>
#include <memory>
#include <stdexcept>
 
enum class Direction { LEFT, RIGHT };
 
struct TreeNode {
    int value;
    std::shared_ptr<TreeNode> left;
    std::shared_ptr<TreeNode> right;
 
    TreeNode(int val, std::shared_ptr<TreeNode> l = nullptr, std::shared_ptr<TreeNode> r = nullptr)
        : value(val), left(l), right(r) {}
};
 
struct Breadcrumb {
    Direction direction;
    int parent_value;
    std::shared_ptr<TreeNode> sibling;
 
    Breadcrumb(Direction dir, int parentVal, std::shared_ptr<TreeNode> sib)
        : direction(dir), parent_value(parentVal), sibling(sib) {}
};
 
class TreeZipper {
private:
    std::shared_ptr<TreeNode> focus;
    std::vector<Breadcrumb> breadcrumbs;
 
public:
    TreeZipper(std::shared_ptr<TreeNode> f, std::vector<Breadcrumb> crumbs = {})
        : focus(f), breadcrumbs(crumbs) {}
 
    std::shared_ptr<TreeNode> getFocus() const { return focus; }
 
    TreeZipper goLeft() const {
        if (!focus || !focus->left) {
            throw std::runtime_error("Cannot move left: Left child does not exist");
        }
        std::vector<Breadcrumb> newCrumbs = breadcrumbs;
        newCrumbs.push_back(Breadcrumb(Direction::LEFT, focus->value, focus->right));
        return TreeZipper(focus->left, newCrumbs);
    }
 
    TreeZipper goRight() const {
        if (!focus || !focus->right) {
            throw std::runtime_error("Cannot move right: Right child does not exist");
        }
        std::vector<Breadcrumb> newCrumbs = breadcrumbs;
        newCrumbs.push_back(Breadcrumb(Direction::RIGHT, focus->value, focus->left));
        return TreeZipper(focus->right, newCrumbs);
    }
 
    TreeZipper goUp() const {
        if (breadcrumbs.empty()) {
            throw std::runtime_error("Cannot move up: Already at the root");
        }
        
        Breadcrumb lastCrumb = breadcrumbs.back();
        std::vector<Breadcrumb> newCrumbs(breadcrumbs.begin(), breadcrumbs.end() - 1);
        
        std::shared_ptr<TreeNode> parentNode;
        if (lastCrumb.direction == Direction::LEFT) {
            parentNode = std::make_shared<TreeNode>(lastCrumb.parent_value, focus, lastCrumb.sibling);
        } else {
            parentNode = std::make_shared<TreeNode>(lastCrumb.parent_value, lastCrumb.sibling, focus);
        }
        return TreeZipper(parentNode, newCrumbs);
    }
 
    TreeZipper update(int newValue) const {
        std::shared_ptr<TreeNode> newFocus;
        if (!focus) {
            newFocus = std::make_shared<TreeNode>(newValue);
        } else {
            newFocus = std::make_shared<TreeNode>(newValue, focus->left, focus->right);
        }
        return TreeZipper(newFocus, breadcrumbs);
    }
 
    std::shared_ptr<TreeNode> toRoot() const {
        TreeZipper temp = *this;
        while (!temp.breadcrumbs.empty()) {
            temp = temp.goUp();
        }
        return temp.focus;
    }
};
 
void printTree(const std::shared_ptr<TreeNode>& node) {
    if (!node) return;
    std::cout << "Node(" << node->value << ", ";
    if (node->left) printTree(node->left);
    else std::cout << "null";
    std::cout << ", ";
    if (node->right) printTree(node->right);
    else std::cout << "null";
    std::cout << ")";
}
 
int main() {
    auto root = std::make_shared<TreeNode>(1, std::make_shared<TreeNode>(2), std::make_shared<TreeNode>(3));
    TreeZipper zipper(root);
 
    zipper = zipper.goLeft().update(99);
    auto newRoot = zipper.toRoot();
 
    std::cout << "Reconstructed Tree: ";
    printTree(newRoot);
    std::cout << "\n"; // Node(1, Node(99, null, null), Node(3, null, null))
    return 0;
}

When to Use

✅ Use Zippers When:

You are implementing tree-navigation features inside a purely functional programming language (like Haskell or Clojure).
You need to perform localized, high-frequency tree edits (e.g. text/source-code syntax tree parsing, XML/HTML nodes editing, directory structure browsers).
Rebuilding entire paths from the root down to make minor local adjustments is too expensive.

❌ Do NOT Use Zippers When:

You are programming in an imperative language (Python, C++, Java) where data structures are naturally mutable. In-place changes are faster.
You require direct, random access to non-adjacent tree components in parallel.

List Zipper: A simpler variant tracking a focused item in a linear list. Represented as two lists: (items_before, focus, items_after). Moving left pops from items_before and pushes to items_after. Useful for text editor line buffers.
Finger Tree: A functional sequence implementation offering amortized $O (1)$ access at both ends, generalization of zippers.

Table of Contents

Explorer

Zipper

Explanation

Real-World Analogy

How It Works

Core Mechanics

1. Tree Node Structure

2. Breadcrumb (Context element)

3. Zipper Operations

Visual Walkthrough

Tree structure: Root (1) with left (2) and right (3)

Zipper initialized at Root (1)

Move Left (go_left())

Update node value to 99 (update(99))

Move Up (go_up())

Time & Space Complexity

Implementation

When to Use

✅ Use Zippers When:

❌ Do NOT Use Zippers When:

Variations & Related Concepts

Key Takeaways

More Learn

GitHub & Webs

Enjoying the Notes?

Graph View

Backlinks

Recently Updated

Move Left (`go_left()`)

Update node value to 99 (`update(99)`)

Move Up (`go_up()`)