272 Advanced

Tree Zipper

TreesFunctional Data StructuresZippers

Tutorial Video

Text description (accessibility)

This video demonstrates the "Tree Zipper" functional Rust example. Difficulty level: Advanced. Key concepts covered: Trees, Functional Data Structures, Zippers. Implement a *zipper* for binary trees: a data structure that tracks a focused subtree together with a breadcrumb trail back to the root, enabling O(1) local navigation (`go_left`, `go_right`, `go_up`) and functional in-place editing (`set_value`) without mutating the original tree. Key difference from OCaml: 1. **Ownership vs. copying:** OCaml copies the record on each navigation step; Rust

Tutorial

The Problem

Implement a zipper for binary trees: a data structure that tracks a focused subtree together with a breadcrumb trail back to the root, enabling O(1) local navigation (go_left, go_right, go_up) and functional in-place editing (set_value) without mutating the original tree.

🎯 Learning Outcomes

• How zippers decompose a tree into a focus and a context (trail of crumbs)

• How Rust's ownership model shapes the API — consuming Zipper<T> by value makes navigation safe and allocation-free

• Why Rust requires an iterative to_tree loop where OCaml can express the same idea as a one-liner (match go_up z with None -> z.focus | Some z' -> to_tree z')

• That functional "editing" means constructing a new path on the way back up, leaving the old tree intact

🦀 The Rust Way

Rust models the same structure with an owned Zipper<T> (focus + Vec<Crumb<T>>). go_left / go_right / go_up consume the zipper and return Option<Zipper<T>>, making the state transition explicit in the type. Because go_up moves z, to_tree cannot read z.focus after the call; instead it checks z.trail.is_empty() first and loops, which is both idiomatic and tail-call-free in practice.

Code Example

#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(Box<Tree<T>>, T, Box<Tree<T>>),
}

#[derive(Debug, Clone)]
pub enum Crumb<T> {
    Left(T, Tree<T>),
    Right(Tree<T>, T),
}

#[derive(Debug, Clone)]
pub struct Zipper<T> {
    pub focus: Tree<T>,
    pub trail: Vec<Crumb<T>>,
}

pub fn go_up<T>(mut z: Zipper<T>) -> Option<Zipper<T>> {
    match z.trail.pop() {
        None => None,
        Some(Crumb::Left(v, r)) => Some(Zipper {
            focus: Tree::node(z.focus, v, r),
            trail: z.trail,
        }),
        Some(Crumb::Right(l, v)) => Some(Zipper {
            focus: Tree::node(l, v, z.focus),
            trail: z.trail,
        }),
    }
}

// Idiomatic: loop + early return avoids the ownership issue
pub fn to_tree<T>(mut z: Zipper<T>) -> Tree<T> {
    loop {
        if z.trail.is_empty() {
            return z.focus;
        }
        z = go_up(z).expect("trail was non-empty");
    }
}

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

type 'a crumb = Left of 'a * 'a tree | Right of 'a tree * 'a
type 'a zipper = { focus: 'a tree; trail: 'a crumb list }

let of_tree t = { focus = t; trail = [] }

let go_left z = match z.focus with
  | Leaf -> None
  | Node (l, v, r) -> Some { focus = l; trail = Left (v, r) :: z.trail }

let go_up z = match z.trail with
  | [] -> None
  | Left (v, r) :: rest -> Some { focus = Node (z.focus, v, r); trail = rest }
  | Right (l, v) :: rest -> Some { focus = Node (l, v, z.focus); trail = rest }

let set_value x z = match z.focus with
  | Leaf -> z
  | Node (l, _, r) -> { z with focus = Node (l, x, r) }

let rec to_tree z = match go_up z with
  | None    -> z.focus
  | Some z' -> to_tree z'

Key Differences

Ownership vs. copying: OCaml copies the record on each navigation step; Rust

moves it, making it clear that the old zipper is consumed and the new one is returned.

Trail representation: OCaml uses a linked list (cons-prepend); Rust uses a

Vec (push/pop), which is more cache-friendly and avoids allocation per step.

**to_tree idiom:** OCaml can read z.focus after go_up z in the same match;

Rust requires checking z.trail.is_empty() before calling go_up because go_up consumes z.

Null safety: Both languages return Option for navigation — the only

difference is syntax (None/Some is identical; OCaml's Option.get vs. Rust's .expect()).

OCaml Approach

OCaml uses a record { focus: 'a tree; trail: 'a crumb list } with a prepend-cons trail. Each navigation function returns an option zipper. Because OCaml passes records by value (copying), go_up can pattern-match on go_up z and still reference z.focus in the None branch — the compiler has no ownership concern.

Full Source

#![allow(clippy::all)]
/// A binary tree — either a Leaf (empty) or a Node with left subtree, value, right subtree.
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(Box<Tree<T>>, T, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn node(left: Tree<T>, val: T, right: Tree<T>) -> Self {
        Tree::Node(Box::new(left), val, Box::new(right))
    }
}

/// A crumb records which direction we descended and what we left behind.
/// Left(v, r)  — we went left; parent had value v and right subtree r
/// Right(l, v) — we went right; parent had left subtree l and value v
#[derive(Debug, Clone)]
pub enum Crumb<T> {
    Left(T, Tree<T>),
    Right(Tree<T>, T),
}

/// A zipper: a focused subtree plus the breadcrumb trail back to the root.
/// Navigation is O(1); rebuilding the whole tree is O(depth).
#[derive(Debug, Clone)]
pub struct Zipper<T> {
    pub focus: Tree<T>,
    pub trail: Vec<Crumb<T>>,
}

/// Wrap a tree in a zipper focused on the root.
pub fn of_tree<T>(tree: Tree<T>) -> Zipper<T> {
    Zipper {
        focus: tree,
        trail: Vec::new(),
    }
}

/// Move focus to the left child. Returns None if focused on a Leaf.
pub fn go_left<T>(mut z: Zipper<T>) -> Option<Zipper<T>> {
    match z.focus {
        Tree::Leaf => None,
        Tree::Node(l, v, r) => {
            z.trail.push(Crumb::Left(v, *r));
            Some(Zipper {
                focus: *l,
                trail: z.trail,
            })
        }
    }
}

/// Move focus to the right child. Returns None if focused on a Leaf.
pub fn go_right<T>(mut z: Zipper<T>) -> Option<Zipper<T>> {
    match z.focus {
        Tree::Leaf => None,
        Tree::Node(l, v, r) => {
            z.trail.push(Crumb::Right(*l, v));
            Some(Zipper {
                focus: *r,
                trail: z.trail,
            })
        }
    }
}

/// Move focus to the parent. Returns None if already at the root.
pub fn go_up<T>(mut z: Zipper<T>) -> Option<Zipper<T>> {
    match z.trail.pop() {
        None => None,
        Some(Crumb::Left(v, r)) => Some(Zipper {
            focus: Tree::node(z.focus, v, r),
            trail: z.trail,
        }),
        Some(Crumb::Right(l, v)) => Some(Zipper {
            focus: Tree::node(l, v, z.focus),
            trail: z.trail,
        }),
    }
}

/// Replace the value at the current focus (no-op if focused on a Leaf).
pub fn set_value<T>(x: T, z: Zipper<T>) -> Zipper<T> {
    match z.focus {
        Tree::Leaf => z,
        Tree::Node(l, _, r) => Zipper {
            focus: Tree::node(*l, x, *r),
            trail: z.trail,
        },
    }
}

/// Climb back to the root and return the reconstructed tree (idiomatic iterative).
///
/// Note: in OCaml `to_tree` can be written as a one-liner because the language
/// lets you read `z.focus` after passing `z` to `go_up` in the same match.
/// In Rust, `go_up` consumes `z` by value, so we must save the focus *before*
/// calling `go_up`, which is clearest expressed as a loop.
pub fn to_tree<T>(mut z: Zipper<T>) -> Tree<T> {
    loop {
        if z.trail.is_empty() {
            return z.focus;
        }
        z = go_up(z).expect("trail was non-empty");
    }
}

/// Climb back to the root — explicit recursion mirrors the OCaml original.
pub fn to_tree_recursive<T>(z: Zipper<T>) -> Tree<T> {
    if z.trail.is_empty() {
        return z.focus;
    }
    to_tree_recursive(go_up(z).expect("trail was non-empty"))
}

#[cfg(test)]
mod tests {
    use super::*;

    fn sample_tree() -> Tree<i32> {
        // Node(Node(Leaf,1,Leaf), 2, Node(Leaf,3,Leaf))
        Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        )
    }

    #[test]
    fn test_of_tree_is_root() {
        let z = of_tree(sample_tree());
        assert!(z.trail.is_empty());
    }

    #[test]
    fn test_go_left_moves_focus() {
        let z = of_tree(sample_tree());
        let z = go_left(z).expect("should have left child");
        assert_eq!(z.focus, Tree::node(Tree::Leaf, 1, Tree::Leaf));
        assert_eq!(z.trail.len(), 1);
    }

    #[test]
    fn test_go_right_moves_focus() {
        let z = of_tree(sample_tree());
        let z = go_right(z).expect("should have right child");
        assert_eq!(z.focus, Tree::node(Tree::Leaf, 3, Tree::Leaf));
        assert_eq!(z.trail.len(), 1);
    }

    #[test]
    fn test_go_left_then_up_returns_root() {
        let z = of_tree(sample_tree());
        let z = go_left(z).expect("left");
        let z = go_up(z).expect("up");
        assert_eq!(z.focus, sample_tree());
        assert!(z.trail.is_empty());
    }

    #[test]
    fn test_go_right_then_up_returns_root() {
        let z = of_tree(sample_tree());
        let z = go_right(z).expect("right");
        let z = go_up(z).expect("up");
        assert_eq!(z.focus, sample_tree());
        assert!(z.trail.is_empty());
    }

    #[test]
    fn test_set_value_updates_focused_node() {
        let z = of_tree(sample_tree());
        let z = go_left(z).expect("left");
        let z = set_value(10, z);
        assert_eq!(z.focus, Tree::node(Tree::Leaf, 10, Tree::Leaf));
    }

    #[test]
    fn test_set_value_on_leaf_is_noop() {
        let z: Zipper<i32> = of_tree(Tree::Leaf);
        let z2 = set_value(42, z);
        assert_eq!(z2.focus, Tree::Leaf);
    }

    #[test]
    fn test_to_tree_rebuilds_after_edit() {
        let z = of_tree(sample_tree());
        let z = go_left(z).expect("left");
        let z = set_value(10, z);
        let result = to_tree(z);
        let expected = Tree::node(
            Tree::node(Tree::Leaf, 10, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        );
        assert_eq!(result, expected);
    }

    #[test]
    fn test_to_tree_recursive_matches_iter() {
        let z = of_tree(sample_tree());
        let z = go_right(z).expect("right");
        let z = set_value(30, z);
        let result = to_tree_recursive(z);
        let expected = Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 30, Tree::Leaf),
        );
        assert_eq!(result, expected);
    }

    #[test]
    fn test_go_left_on_leaf_returns_none() {
        let z: Zipper<i32> = of_tree(Tree::Leaf);
        assert!(go_left(z).is_none());
    }

    #[test]
    fn test_go_up_at_root_returns_none() {
        let z = of_tree(sample_tree());
        assert!(go_up(z).is_none());
    }

    #[test]
    fn test_deep_navigation_and_edit() {
        // Build a 3-level tree: root=5, left subtree root=3, its left child=1
        let tree = Tree::node(
            Tree::node(Tree::node(Tree::Leaf, 1, Tree::Leaf), 3, Tree::Leaf),
            5,
            Tree::Leaf,
        );
        let z = of_tree(tree);
        let z = go_left(z).expect("left");
        let z = go_left(z).expect("left-left");
        let z = set_value(99, z);
        let result = to_tree(z);
        let expected = Tree::node(
            Tree::node(Tree::node(Tree::Leaf, 99, Tree::Leaf), 3, Tree::Leaf),
            5,
            Tree::Leaf,
        );
        assert_eq!(result, expected);
    }
}

(* Tree zipper — O(1) local navigation and functional editing *)

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

(* A crumb records the direction taken and what was left behind *)
type 'a crumb = Left of 'a * 'a tree | Right of 'a tree * 'a
type 'a zipper = { focus: 'a tree; trail: 'a crumb list }

(* --- Navigation --- *)

let of_tree t = { focus = t; trail = [] }

let go_left z = match z.focus with
  | Leaf -> None
  | Node (l, v, r) -> Some { focus = l; trail = Left (v, r) :: z.trail }

let go_right z = match z.focus with
  | Leaf -> None
  | Node (l, v, r) -> Some { focus = r; trail = Right (l, v) :: z.trail }

let go_up z = match z.trail with
  | [] -> None
  | Left (v, r) :: rest -> Some { focus = Node (z.focus, v, r); trail = rest }
  | Right (l, v) :: rest -> Some { focus = Node (l, v, z.focus); trail = rest }

(* --- Editing --- *)

let set_value x z = match z.focus with
  | Leaf -> z
  | Node (l, _, r) -> { z with focus = Node (l, x, r) }

(* Idiomatic: climb to root using tail recursion *)
let rec to_tree z = match go_up z with
  | None    -> z.focus
  | Some z' -> to_tree z'

(* --- Tests --- *)

let () =
  let tree = Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)) in
  let z = of_tree tree in

  (* go_left moves focus to left child *)
  let z_left = Option.get (go_left z) in
  assert (z_left.focus = Node (Leaf, 1, Leaf));

  (* go_right moves focus to right child *)
  let z_right = Option.get (go_right z) in
  assert (z_right.focus = Node (Leaf, 3, Leaf));

  (* go_up after go_left reconstructs root *)
  let z_up = Option.get (go_up z_left) in
  assert (z_up.focus = tree);

  (* set_value then to_tree rebuilds whole tree *)
  let z_edited = set_value 10 z_left in
  let result = to_tree z_edited in
  assert (result = Node (Node (Leaf, 10, Leaf), 2, Node (Leaf, 3, Leaf)));

  (* go_left on Leaf returns None *)
  assert (go_left { focus = Leaf; trail = [] } = None);

  (* go_up at root returns None *)
  assert (go_up { focus = tree; trail = [] } = None);

  ignore z_right;
  print_endline "ok"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    fn sample_tree() -> Tree<i32> {
        // Node(Node(Leaf,1,Leaf), 2, Node(Leaf,3,Leaf))
        Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        )
    }

    #[test]
    fn test_of_tree_is_root() {
        let z = of_tree(sample_tree());
        assert!(z.trail.is_empty());
    }

    #[test]
    fn test_go_left_moves_focus() {
        let z = of_tree(sample_tree());
        let z = go_left(z).expect("should have left child");
        assert_eq!(z.focus, Tree::node(Tree::Leaf, 1, Tree::Leaf));
        assert_eq!(z.trail.len(), 1);
    }

    #[test]
    fn test_go_right_moves_focus() {
        let z = of_tree(sample_tree());
        let z = go_right(z).expect("should have right child");
        assert_eq!(z.focus, Tree::node(Tree::Leaf, 3, Tree::Leaf));
        assert_eq!(z.trail.len(), 1);
    }

    #[test]
    fn test_go_left_then_up_returns_root() {
        let z = of_tree(sample_tree());
        let z = go_left(z).expect("left");
        let z = go_up(z).expect("up");
        assert_eq!(z.focus, sample_tree());
        assert!(z.trail.is_empty());
    }

    #[test]
    fn test_go_right_then_up_returns_root() {
        let z = of_tree(sample_tree());
        let z = go_right(z).expect("right");
        let z = go_up(z).expect("up");
        assert_eq!(z.focus, sample_tree());
        assert!(z.trail.is_empty());
    }

    #[test]
    fn test_set_value_updates_focused_node() {
        let z = of_tree(sample_tree());
        let z = go_left(z).expect("left");
        let z = set_value(10, z);
        assert_eq!(z.focus, Tree::node(Tree::Leaf, 10, Tree::Leaf));
    }

    #[test]
    fn test_set_value_on_leaf_is_noop() {
        let z: Zipper<i32> = of_tree(Tree::Leaf);
        let z2 = set_value(42, z);
        assert_eq!(z2.focus, Tree::Leaf);
    }

    #[test]
    fn test_to_tree_rebuilds_after_edit() {
        let z = of_tree(sample_tree());
        let z = go_left(z).expect("left");
        let z = set_value(10, z);
        let result = to_tree(z);
        let expected = Tree::node(
            Tree::node(Tree::Leaf, 10, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        );
        assert_eq!(result, expected);
    }

    #[test]
    fn test_to_tree_recursive_matches_iter() {
        let z = of_tree(sample_tree());
        let z = go_right(z).expect("right");
        let z = set_value(30, z);
        let result = to_tree_recursive(z);
        let expected = Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 30, Tree::Leaf),
        );
        assert_eq!(result, expected);
    }

    #[test]
    fn test_go_left_on_leaf_returns_none() {
        let z: Zipper<i32> = of_tree(Tree::Leaf);
        assert!(go_left(z).is_none());
    }

    #[test]
    fn test_go_up_at_root_returns_none() {
        let z = of_tree(sample_tree());
        assert!(go_up(z).is_none());
    }

    #[test]
    fn test_deep_navigation_and_edit() {
        // Build a 3-level tree: root=5, left subtree root=3, its left child=1
        let tree = Tree::node(
            Tree::node(Tree::node(Tree::Leaf, 1, Tree::Leaf), 3, Tree::Leaf),
            5,
            Tree::Leaf,
        );
        let z = of_tree(tree);
        let z = go_left(z).expect("left");
        let z = go_left(z).expect("left-left");
        let z = set_value(99, z);
        let result = to_tree(z);
        let expected = Tree::node(
            Tree::node(Tree::node(Tree::Leaf, 99, Tree::Leaf), 3, Tree::Leaf),
            5,
            Tree::Leaf,
        );
        assert_eq!(result, expected);
    }
}

Deep Comparison

OCaml vs Rust: Tree Zipper

Side-by-Side Code

OCaml

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

type 'a crumb = Left of 'a * 'a tree | Right of 'a tree * 'a
type 'a zipper = { focus: 'a tree; trail: 'a crumb list }

let of_tree t = { focus = t; trail = [] }

let go_left z = match z.focus with
  | Leaf -> None
  | Node (l, v, r) -> Some { focus = l; trail = Left (v, r) :: z.trail }

let go_up z = match z.trail with
  | [] -> None
  | Left (v, r) :: rest -> Some { focus = Node (z.focus, v, r); trail = rest }
  | Right (l, v) :: rest -> Some { focus = Node (l, v, z.focus); trail = rest }

let set_value x z = match z.focus with
  | Leaf -> z
  | Node (l, _, r) -> { z with focus = Node (l, x, r) }

let rec to_tree z = match go_up z with
  | None    -> z.focus
  | Some z' -> to_tree z'

Rust (idiomatic — iterative `to_tree`)

#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(Box<Tree<T>>, T, Box<Tree<T>>),
}

#[derive(Debug, Clone)]
pub enum Crumb<T> {
    Left(T, Tree<T>),
    Right(Tree<T>, T),
}

#[derive(Debug, Clone)]
pub struct Zipper<T> {
    pub focus: Tree<T>,
    pub trail: Vec<Crumb<T>>,
}

pub fn go_up<T>(mut z: Zipper<T>) -> Option<Zipper<T>> {
    match z.trail.pop() {
        None => None,
        Some(Crumb::Left(v, r)) => Some(Zipper {
            focus: Tree::node(z.focus, v, r),
            trail: z.trail,
        }),
        Some(Crumb::Right(l, v)) => Some(Zipper {
            focus: Tree::node(l, v, z.focus),
            trail: z.trail,
        }),
    }
}

// Idiomatic: loop + early return avoids the ownership issue
pub fn to_tree<T>(mut z: Zipper<T>) -> Tree<T> {
    loop {
        if z.trail.is_empty() {
            return z.focus;
        }
        z = go_up(z).expect("trail was non-empty");
    }
}

Rust (functional/recursive)

// Mirrors the OCaml tail-recursive style
pub fn to_tree_recursive<T>(z: Zipper<T>) -> Tree<T> {
    if z.trail.is_empty() {
        return z.focus;
    }
    to_tree_recursive(go_up(z).expect("trail was non-empty"))
}

Type Signatures

Concept	OCaml	Rust
Tree type	`'a tree = Leaf \\| Node of 'a tree * 'a * 'a tree`	`enum Tree<T> { Leaf, Node(Box<Tree<T>>, T, Box<Tree<T>>) }`
Crumb type	`'a crumb = Left of 'a * 'a tree \\| Right of 'a tree * 'a`	`enum Crumb<T> { Left(T, Tree<T>), Right(Tree<T>, T) }`
Zipper type	`'a zipper = { focus: 'a tree; trail: 'a crumb list }`	`struct Zipper<T> { focus: Tree<T>, trail: Vec<Crumb<T>> }`
`go_left`	`'a zipper -> 'a zipper option`	`fn go_left<T>(z: Zipper<T>) -> Option<Zipper<T>>`
`set_value`	`'a -> 'a zipper -> 'a zipper`	`fn set_value<T>(x: T, z: Zipper<T>) -> Zipper<T>`
`to_tree`	`'a zipper -> 'a tree`	`fn to_tree<T>(z: Zipper<T>) -> Tree<T>`

Key Insights

Ownership makes state transitions explicit. OCaml passes the zipper record by

value implicitly; Rust's move semantics make the same transfer explicit — you hand over the old Zipper<T> and receive a new one. This prevents accidentally using a stale zipper after navigation.

**The to_tree one-liner breaks in Rust.** OCaml can write

match go_up z with
   None -> z.focus | Some z' -> to_tree z'

because the match does not consume

z in a way that prevents reading z.focus. In Rust, go_up(z) moves z, so z.focus is inaccessible in the None arm. The fix is to check the trail before calling go_up, which is equally clear and efficient.

**Vec vs. linked list for the trail.** OCaml's natural crumb list is a linked

list (cons-cells, O(1) prepend). Rust's Vec uses push/pop at the end — also O(1) amortised, but with better cache locality and no per-node allocation.

**Box for recursive ADTs.** OCaml trees have a uniform heap layout; Rust

enums must have a known size, so recursive variants need Box<Tree<T>> to break the infinite-size cycle. This is the canonical Rust pattern for recursive data structures.

**{ z with focus = … } vs. struct update.** OCaml's record update syntax

({ z with focus = Node ... }) has a direct Rust analogue in struct update syntax (Zipper { focus: …, ..z }), but since z is consumed by move we instead destructure it manually — which is equally concise.

When to Use Each Style

**Use idiomatic Rust (to_tree loop) when:** you want to avoid potential stack overflow on deep trees, since Rust does not guarantee tail-call optimisation.

**Use recursive Rust (to_tree_recursive) when:** the tree depth is bounded and you want the code to read as closely as possible to the OCaml original for educational or porting purposes.

Exercises

Implement navigate_right and navigate_left for the tree zipper, enabling horizontal movement between siblings.

Write a map_focused function that applies a transformation to the currently focused node and returns the updated zipper.

Build a simple tree editor using the zipper: support commands up, down_left, down_right, insert_left, insert_right, and delete_focus, reconstructing the full tree after a sequence of operations.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust