Tree Zipper

---
name: tree-zipper
description: "Navigate immutable trees with a zipper cursor. Use when implementing tree traversal, editing tree structures functionally, or tracking focus through breadcrumbs."
topic: Functional Tree Navigation
token_cost: 130
related: [tree-rerooting, dfs-vs-bfs]
keywords:
  [
    zipper,
    tree navigation,
    breadcrumb,
    focus,
    up,
    down,
    left,
    right,
    functional tree,
    immutable tree,
    cursor,
  ]
---

## When to use

A tree zipper is a cursor for immutable trees. State = (focus, trail).

## Rules

- focus is the current subtree
- trail is a list of "breadcrumbs" describing the path from root to focus
- Each crumb remembers the parent's value plus the siblings NOT taken
- down_left/down_right push a crumb and make the chosen child the new focus
- up pops the top crumb, rebuilds the parent, and makes that parent the new focus
- set_value replaces the focused subtree's value
- to_tree walks all the way up to rebuild the whole tree
- Key invariant: you can ALWAYS reconstruct the full original tree from (focus, trail)
- Equality of two zippers = equality of the fully-reconstructed trees, NOT of the raw (focus, trail) pairs
- NEVER compare raw (focus, trail) pairs for equality

## Operations

down_left, down_right, up, set_value, to_tree.

## Example

Navigate: `z.down_left()` pushes a crumb (parent value + right siblings), sets focus to left child. `z.up()` pops crumb, rebuilds parent. `z.to_tree()` walks all the way up. Compare zippers by `to_tree()` equality, never raw (focus, trail).