972 Advanced

972 Persistent Tree

Functional Programming

Tutorial

The Problem

Implement a persistent binary search tree where insert and delete return new tree versions sharing unchanged subtrees via Rc. Only the nodes along the modified path are newly allocated; nodes not on the insertion path are shared between old and new versions. This is the Rust analog of OCaml's immutable BST.

🎯 Learning Outcomes

• Define enum Bst<T> { Empty, Node(Rc<Bst<T>>, T, Rc<Bst<T>>) } with Rc for child sharing

• Implement insert(&self, x: T) -> Bst<T> that allocates new nodes only on the path to the insertion point and Rc::clones the unchanged subtree

• Implement member(&self, x: &T) -> bool as a simple recursive search

• Implement min_val(&self) -> Option<&T> by descending left until Empty

• Understand why Bst itself is Clone (not wrapped in Rc) — callers hold Bst<T> directly; Rc is used for internal child references

Code Example

#![allow(clippy::all)]
// 972: Persistent Binary Search Tree
// Functional update: insert/delete return new Rc-shared trees
// Shared nodes between versions via Rc<BstNode<T>>

use std::rc::Rc;

#[derive(Debug, Clone, PartialEq)]
pub enum Bst<T> {
    Empty,
    Node(Rc<Bst<T>>, T, Rc<Bst<T>>),
}

impl<T: Ord + Clone> Bst<T> {
    pub fn empty() -> Self {
        Bst::Empty
    }

    /// Insert returns a new tree sharing unchanged subtrees
    pub fn insert(&self, x: T) -> Self {
        match self {
            Bst::Empty => Bst::Node(Rc::new(Bst::Empty), x, Rc::new(Bst::Empty)),
            Bst::Node(l, v, r) => {
                if x < *v {
                    Bst::Node(Rc::new(l.insert(x)), v.clone(), Rc::clone(r))
                } else if x > *v {
                    Bst::Node(Rc::clone(l), v.clone(), Rc::new(r.insert(x)))
                } else {
                    self.clone() // duplicate: return same (Rc-shared)
                }
            }
        }
    }

    pub fn member(&self, x: &T) -> bool {
        match self {
            Bst::Empty => false,
            Bst::Node(l, v, r) => {
                if x == v {
                    true
                } else if x < v {
                    l.member(x)
                } else {
                    r.member(x)
                }
            }
        }
    }

    pub fn min_val(&self) -> Option<&T> {
        match self {
            Bst::Empty => None,
            Bst::Node(l, v, _) => {
                if matches!(l.as_ref(), Bst::Empty) {
                    Some(v)
                } else {
                    l.min_val()
                }
            }
        }
    }

    /// Delete returns a new tree, old tree unchanged
    pub fn delete(&self, x: &T) -> Self {
        match self {
            Bst::Empty => Bst::Empty,
            Bst::Node(l, v, r) => {
                if x < v {
                    Bst::Node(Rc::new(l.delete(x)), v.clone(), Rc::clone(r))
                } else if x > v {
                    Bst::Node(Rc::clone(l), v.clone(), Rc::new(r.delete(x)))
                } else {
                    // Found node: replace with min of right subtree
                    match r.min_val() {
                        None => (**l).clone(), // no right subtree
                        Some(m) => {
                            let m = m.clone();
                            let new_r = r.delete(&m);
                            Bst::Node(Rc::clone(l), m, Rc::new(new_r))
                        }
                    }
                }
            }
        }
    }

    pub fn to_vec(&self) -> Vec<T> {
        match self {
            Bst::Empty => vec![],
            Bst::Node(l, v, r) => {
                let mut result = l.to_vec();
                result.push(v.clone());
                result.extend(r.to_vec());
                result
            }
        }
    }
}

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

    fn make_tree() -> Bst<i32> {
        Bst::empty()
            .insert(5)
            .insert(3)
            .insert(7)
            .insert(1)
            .insert(4)
    }

    #[test]
    fn test_insert_sorted() {
        let t = make_tree();
        assert_eq!(t.to_vec(), vec![1, 3, 4, 5, 7]);
    }

    #[test]
    fn test_persistence() {
        let t0 = Bst::empty().insert(5).insert(3).insert(7).insert(1);
        let t1 = t0.insert(4);
        // t0 is unchanged
        assert_eq!(t0.to_vec(), vec![1, 3, 5, 7]);
        assert_eq!(t1.to_vec(), vec![1, 3, 4, 5, 7]);
    }

    #[test]
    fn test_member() {
        let t = make_tree();
        assert!(t.member(&4));
        assert!(t.member(&5));
        assert!(!t.member(&2));
        assert!(!t.member(&6));
    }

    #[test]
    fn test_delete_leaf() {
        let t = make_tree();
        let t2 = t.delete(&1);
        assert_eq!(t2.to_vec(), vec![3, 4, 5, 7]);
        assert_eq!(t.to_vec(), vec![1, 3, 4, 5, 7]); // unchanged
    }

    #[test]
    fn test_delete_internal() {
        let t = make_tree();
        let t2 = t.delete(&3);
        assert_eq!(t2.to_vec(), vec![1, 4, 5, 7]);

        let t3 = t.delete(&5); // delete root
        assert_eq!(t3.to_vec(), vec![1, 3, 4, 7]);
    }
}

(* 972: Persistent Binary Search Tree *)
(* Functional update: insert/delete return new root, old tree unchanged *)

type 'a bst =
  | Empty
  | Node of 'a bst * 'a * 'a bst

(* Approach 1: Insert returns new tree (functional style) *)

let rec insert tree x =
  match tree with
  | Empty -> Node (Empty, x, Empty)
  | Node (l, v, r) ->
    if x < v then Node (insert l x, v, r)
    else if x > v then Node (l, v, insert r x)
    else tree  (* duplicate: return same tree *)

let rec member tree x =
  match tree with
  | Empty -> false
  | Node (l, v, r) ->
    if x = v then true
    else if x < v then member l x
    else member r x

let rec min_val = function
  | Empty -> None
  | Node (Empty, v, _) -> Some v
  | Node (l, _, _) -> min_val l

(* Approach 2: Functional delete *)

let rec delete tree x =
  match tree with
  | Empty -> Empty
  | Node (l, v, r) ->
    if x < v then Node (delete l x, v, r)
    else if x > v then Node (l, v, delete r x)
    else
      (* Found: merge left and right subtrees *)
      match min_val r with
      | None -> l  (* no right subtree *)
      | Some m -> Node (l, m, delete r m)

let rec to_list tree =
  match tree with
  | Empty -> []
  | Node (l, v, r) -> to_list l @ [v] @ to_list r

let () =
  let t0 = Empty in
  let t1 = insert t0 5 in
  let t2 = insert t1 3 in
  let t3 = insert t2 7 in
  let t4 = insert t3 1 in
  let t5 = insert t4 4 in

  (* t4 still exists unchanged *)
  assert (to_list t4 = [1; 3; 5; 7]);
  assert (to_list t5 = [1; 3; 4; 5; 7]);

  assert (member t5 4);
  assert (member t5 5);
  assert (not (member t5 2));
  assert (not (member t5 6));

  let t6 = delete t5 3 in
  assert (to_list t6 = [1; 4; 5; 7]);
  assert (to_list t5 = [1; 3; 4; 5; 7]);  (* t5 unchanged! *)

  let t7 = delete t5 5 in
  assert (to_list t7 = [1; 3; 4; 7]);

  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Sharing mechanism	`Rc::clone` — explicit O(1)	GC — implicit
`T: Clone` bound	Required to copy `v` into new nodes	No bound; values are copied by the runtime
Duplicate insert	`self.clone()`	Return `t` (same pointer via GC)
Node allocation	`Rc::new(...)`	Constructor (GC managed)

Persistent BSTs are the foundation of OCaml's Map and Set modules. Each Map.add or Set.add returns a new tree sharing unchanged branches — O(log n) allocation, O(log n) lookup.

OCaml Approach

type 'a bst = Empty | Node of 'a bst * 'a * 'a bst

let rec insert x = function
  | Empty -> Node (Empty, x, Empty)
  | Node (l, v, r) as t ->
    if x < v      then Node (insert x l, v, r)  (* r is shared (GC) *)
    else if x > v then Node (l, v, insert x r)  (* l is shared *)
    else t  (* duplicate: return same node (GC shares it) *)

let rec member x = function
  | Empty -> false
  | Node (l, v, r) ->
    if x = v then true
    else if x < v then member x l
    else member x r

OCaml's GC makes structural sharing automatic. Node (insert x l, v, r) shares r without explicit Rc::clone because the GC tracks references. The Rust Rc::clone call is the explicit acknowledgment of the same operation.

Full Source

#![allow(clippy::all)]
// 972: Persistent Binary Search Tree
// Functional update: insert/delete return new Rc-shared trees
// Shared nodes between versions via Rc<BstNode<T>>

use std::rc::Rc;

#[derive(Debug, Clone, PartialEq)]
pub enum Bst<T> {
    Empty,
    Node(Rc<Bst<T>>, T, Rc<Bst<T>>),
}

impl<T: Ord + Clone> Bst<T> {
    pub fn empty() -> Self {
        Bst::Empty
    }

    /// Insert returns a new tree sharing unchanged subtrees
    pub fn insert(&self, x: T) -> Self {
        match self {
            Bst::Empty => Bst::Node(Rc::new(Bst::Empty), x, Rc::new(Bst::Empty)),
            Bst::Node(l, v, r) => {
                if x < *v {
                    Bst::Node(Rc::new(l.insert(x)), v.clone(), Rc::clone(r))
                } else if x > *v {
                    Bst::Node(Rc::clone(l), v.clone(), Rc::new(r.insert(x)))
                } else {
                    self.clone() // duplicate: return same (Rc-shared)
                }
            }
        }
    }

    pub fn member(&self, x: &T) -> bool {
        match self {
            Bst::Empty => false,
            Bst::Node(l, v, r) => {
                if x == v {
                    true
                } else if x < v {
                    l.member(x)
                } else {
                    r.member(x)
                }
            }
        }
    }

    pub fn min_val(&self) -> Option<&T> {
        match self {
            Bst::Empty => None,
            Bst::Node(l, v, _) => {
                if matches!(l.as_ref(), Bst::Empty) {
                    Some(v)
                } else {
                    l.min_val()
                }
            }
        }
    }

    /// Delete returns a new tree, old tree unchanged
    pub fn delete(&self, x: &T) -> Self {
        match self {
            Bst::Empty => Bst::Empty,
            Bst::Node(l, v, r) => {
                if x < v {
                    Bst::Node(Rc::new(l.delete(x)), v.clone(), Rc::clone(r))
                } else if x > v {
                    Bst::Node(Rc::clone(l), v.clone(), Rc::new(r.delete(x)))
                } else {
                    // Found node: replace with min of right subtree
                    match r.min_val() {
                        None => (**l).clone(), // no right subtree
                        Some(m) => {
                            let m = m.clone();
                            let new_r = r.delete(&m);
                            Bst::Node(Rc::clone(l), m, Rc::new(new_r))
                        }
                    }
                }
            }
        }
    }

    pub fn to_vec(&self) -> Vec<T> {
        match self {
            Bst::Empty => vec![],
            Bst::Node(l, v, r) => {
                let mut result = l.to_vec();
                result.push(v.clone());
                result.extend(r.to_vec());
                result
            }
        }
    }
}

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

    fn make_tree() -> Bst<i32> {
        Bst::empty()
            .insert(5)
            .insert(3)
            .insert(7)
            .insert(1)
            .insert(4)
    }

    #[test]
    fn test_insert_sorted() {
        let t = make_tree();
        assert_eq!(t.to_vec(), vec![1, 3, 4, 5, 7]);
    }

    #[test]
    fn test_persistence() {
        let t0 = Bst::empty().insert(5).insert(3).insert(7).insert(1);
        let t1 = t0.insert(4);
        // t0 is unchanged
        assert_eq!(t0.to_vec(), vec![1, 3, 5, 7]);
        assert_eq!(t1.to_vec(), vec![1, 3, 4, 5, 7]);
    }

    #[test]
    fn test_member() {
        let t = make_tree();
        assert!(t.member(&4));
        assert!(t.member(&5));
        assert!(!t.member(&2));
        assert!(!t.member(&6));
    }

    #[test]
    fn test_delete_leaf() {
        let t = make_tree();
        let t2 = t.delete(&1);
        assert_eq!(t2.to_vec(), vec![3, 4, 5, 7]);
        assert_eq!(t.to_vec(), vec![1, 3, 4, 5, 7]); // unchanged
    }

    #[test]
    fn test_delete_internal() {
        let t = make_tree();
        let t2 = t.delete(&3);
        assert_eq!(t2.to_vec(), vec![1, 4, 5, 7]);

        let t3 = t.delete(&5); // delete root
        assert_eq!(t3.to_vec(), vec![1, 3, 4, 7]);
    }
}

(* 972: Persistent Binary Search Tree *)
(* Functional update: insert/delete return new root, old tree unchanged *)

type 'a bst =
  | Empty
  | Node of 'a bst * 'a * 'a bst

(* Approach 1: Insert returns new tree (functional style) *)

let rec insert tree x =
  match tree with
  | Empty -> Node (Empty, x, Empty)
  | Node (l, v, r) ->
    if x < v then Node (insert l x, v, r)
    else if x > v then Node (l, v, insert r x)
    else tree  (* duplicate: return same tree *)

let rec member tree x =
  match tree with
  | Empty -> false
  | Node (l, v, r) ->
    if x = v then true
    else if x < v then member l x
    else member r x

let rec min_val = function
  | Empty -> None
  | Node (Empty, v, _) -> Some v
  | Node (l, _, _) -> min_val l

(* Approach 2: Functional delete *)

let rec delete tree x =
  match tree with
  | Empty -> Empty
  | Node (l, v, r) ->
    if x < v then Node (delete l x, v, r)
    else if x > v then Node (l, v, delete r x)
    else
      (* Found: merge left and right subtrees *)
      match min_val r with
      | None -> l  (* no right subtree *)
      | Some m -> Node (l, m, delete r m)

let rec to_list tree =
  match tree with
  | Empty -> []
  | Node (l, v, r) -> to_list l @ [v] @ to_list r

let () =
  let t0 = Empty in
  let t1 = insert t0 5 in
  let t2 = insert t1 3 in
  let t3 = insert t2 7 in
  let t4 = insert t3 1 in
  let t5 = insert t4 4 in

  (* t4 still exists unchanged *)
  assert (to_list t4 = [1; 3; 5; 7]);
  assert (to_list t5 = [1; 3; 4; 5; 7]);

  assert (member t5 4);
  assert (member t5 5);
  assert (not (member t5 2));
  assert (not (member t5 6));

  let t6 = delete t5 3 in
  assert (to_list t6 = [1; 4; 5; 7]);
  assert (to_list t5 = [1; 3; 4; 5; 7]);  (* t5 unchanged! *)

  let t7 = delete t5 5 in
  assert (to_list t7 = [1; 3; 4; 7]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    fn make_tree() -> Bst<i32> {
        Bst::empty()
            .insert(5)
            .insert(3)
            .insert(7)
            .insert(1)
            .insert(4)
    }

    #[test]
    fn test_insert_sorted() {
        let t = make_tree();
        assert_eq!(t.to_vec(), vec![1, 3, 4, 5, 7]);
    }

    #[test]
    fn test_persistence() {
        let t0 = Bst::empty().insert(5).insert(3).insert(7).insert(1);
        let t1 = t0.insert(4);
        // t0 is unchanged
        assert_eq!(t0.to_vec(), vec![1, 3, 5, 7]);
        assert_eq!(t1.to_vec(), vec![1, 3, 4, 5, 7]);
    }

    #[test]
    fn test_member() {
        let t = make_tree();
        assert!(t.member(&4));
        assert!(t.member(&5));
        assert!(!t.member(&2));
        assert!(!t.member(&6));
    }

    #[test]
    fn test_delete_leaf() {
        let t = make_tree();
        let t2 = t.delete(&1);
        assert_eq!(t2.to_vec(), vec![3, 4, 5, 7]);
        assert_eq!(t.to_vec(), vec![1, 3, 4, 5, 7]); // unchanged
    }

    #[test]
    fn test_delete_internal() {
        let t = make_tree();
        let t2 = t.delete(&3);
        assert_eq!(t2.to_vec(), vec![1, 4, 5, 7]);

        let t3 = t.delete(&5); // delete root
        assert_eq!(t3.to_vec(), vec![1, 3, 4, 7]);
    }
}

Deep Comparison

Persistent BST — Comparison

Core Insight

A persistent BST creates only O(log n) new nodes per operation — the path from root to the changed node. All unchanged subtrees are shared between the old and new versions. OCaml's GC makes this transparent; Rust uses Rc::clone on unchanged subtrees (O(1) pointer copy) and Rc::new(subtree.insert(x)) for the new path.

OCaml Approach

• type 'a bst = Empty | Node of 'a bst * 'a * 'a bst — clean recursive type

• insert l x creates new nodes on the path; unchanged branches reused by GC

• Node (insert l x, v, r) — r is shared (pointer, not copy)

• delete: min_val r to find in-order successor for node removal

• All operations return new trees; old trees remain valid and accessible

• No explicit sharing mechanism — GC handles it

Rust Approach

• enum Bst<T> { Empty, Node(Rc<Bst<T>>, T, Rc<Bst<T>>) } — Rc wraps children

• Rc::clone(r) — O(1) pointer copy, shares unchanged subtree

• Rc::new(l.insert(x)) — allocates new node on changed path only

• (**l).clone() — deref Rc, then clone the Bst (needed for delete leaf case)

• T: Ord + Clone — needed for comparison and copying values into new nodes

• Both old and new trees valid as long as any Rc points to them

Comparison Table

Aspect	OCaml	Rust
Sharing mechanism	GC implicit	`Rc::clone` explicit
New node on path	`Node (insert l x, v, r)`	`Node(Rc::new(l.insert(x)), v.clone(), Rc::clone(r))`
Unchanged branch	Reused automatically	`Rc::clone(branch)` (O(1))
Node lifetime	GC	Rc drops when last ref gone
Trait bounds	None (structural)	`T: Ord + Clone`
Delete successor	`min_val r; delete r m`	`r.min_val(); r.delete(&m)`
New nodes per op	O(log n)	O(log n)

Exercises

Implement delete(&self, x: &T) -> Bst<T> — handle leaf, one-child, and two-child cases.

Implement to_sorted_vec(&self) -> Vec<T> via in-order traversal.

Implement size(&self) -> usize recursively and cache it in Node for O(1) lookup.

Implement a balanced persistent BST by adding AVL or red-black rebalancing to insert.

Verify structural sharing: insert 10 elements, show that each version shares nodes with the previous by comparing Rc::ptr_eq on unchanged subtrees.

Open Source Repos

functional-rust

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

Rust