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).