068: Foldable Tree

Difficulty: 2 Level: Intermediate Implement in-order, pre-order, and post-order folds for a binary tree, then derive aggregations from a single fold primitive.

The Problem This Solves

A binary tree can be traversed in three meaningful ways: in-order (left, root, right — produces sorted order for a BST), pre-order (root, left, right — useful for serialisation), post-order (left, right, root — useful for deletion or evaluation). Each order produces a different sequence from the same structure. Without parameterised folds, you'd write separate recursive functions for every aggregation: `sum_inorder`, `max_inorder`, `to_vec_preorder`, etc. With a fold that takes traversal order as a parameter, you write the traversal once and derive all aggregations by varying the combining function. This is the practical meaning of "fold is universal": every aggregation over a tree — sum, max, any, all, count, to_vec — is a fold with a different initial value and combining function.

The Intuition

Think of a fold as threading a needle through the tree. The traversal order determines the path of the needle (which nodes it visits first). The combining function determines what happens at each node — whether you sum, compare, collect, or test. Change the path (in-order vs pre-order): you get elements in a different sequence. Keep the path, change the combining function: you get a different aggregation. That separation is the power.

How It Works in Rust

impl<T> Tree<T> {
 // In-order: left → root → right (sorted order for BST)
 fn fold_inorder<B>(&self, init: B, f: &mut impl FnMut(B, &T) -> B) -> B {
     match self {
         Tree::Leaf => init,
         Tree::Node(l, v, r) => {
             let acc = l.fold_inorder(init, f);  // visit left subtree
             let acc = f(acc, v);                // visit root
             r.fold_inorder(acc, f)              // visit right subtree
         }
     }
 }
 // Pre-order: root → left → right (swap first two lines above)
 // Post-order: left → right → root (root last)
}

impl Tree<i32> {
 // Everything derived from fold_inorder:
 fn sum(&self)    -> i32         { self.fold_inorder(0,     &mut |acc, x| acc + x) }
 fn max_val(&self) -> Option<i32> { self.fold_inorder(None,  &mut |acc, x| Some(acc.map_or(*x, |a| a.max(*x)))) }
 fn all(&self, pred: impl Fn(&i32) -> bool) -> bool { self.fold_inorder(true, &mut |acc, x| acc && pred(x)) }
 fn count(&self, pred: impl Fn(&i32) -> bool) -> usize { self.fold_inorder(0, &mut |acc, x| if pred(x) { acc + 1 } else { acc }) }
 fn to_vec_inorder(&self) -> Vec<i32> {
     let mut v = Vec::new();
     self.fold_inorder((), &mut |(), x| { v.push(*x); });
     v
 }
}

The `&mut impl FnMut` signature lets the closure be mutated through recursive calls — necessary because the closure captures mutable state (like `&mut Vec`) across the recursion. This is where Rust's borrow checker shapes the API differently from OCaml.

What This Unlocks

BST operations — in-order fold on a sorted binary tree gives you sorted order, enabling range queries and sorted output.
Expression tree evaluation — post-order fold evaluates an AST naturally (children before parent).
Serialisation — pre-order fold produces a prefix notation sequence for compact tree encoding.

Key Differences

Concept	OCaml	Rust
Closure through recursion	Plain function argument	`&mut impl FnMut` (mutable borrow through recursion)
Side-effecting fold	Functional (returns value)	`to_vec_inorder` captures `&mut Vec` in closure
Empty-tree max	`min_int` sentinel	`Option<i32>` — no sentinel needed
Traversal order	Separate functions or parameter	Separate methods (`fold_inorder`, `fold_preorder`, `fold_postorder`)
Tree node allocation	Implicit heap	`Box<Tree<T>>` for recursive fields

// Example 068: Foldable for Binary Tree
// Left/right fold, collect all values, various aggregations

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

impl<T> Tree<T> {
    fn node(l: Tree<T>, v: T, r: Tree<T>) -> Self {
        Tree::Node(Box::new(l), v, Box::new(r))
    }

    // Approach 1: In-order fold
    fn fold_inorder<B>(&self, init: B, f: &mut impl FnMut(B, &T) -> B) -> B {
        match self {
            Tree::Leaf => init,
            Tree::Node(l, v, r) => {
                let acc = l.fold_inorder(init, f);
                let acc = f(acc, v);
                r.fold_inorder(acc, f)
            }
        }
    }

    // Approach 2: Pre-order and post-order
    fn fold_preorder<B>(&self, init: B, f: &mut impl FnMut(B, &T) -> B) -> B {
        match self {
            Tree::Leaf => init,
            Tree::Node(l, v, r) => {
                let acc = f(init, v);
                let acc = l.fold_preorder(acc, f);
                r.fold_preorder(acc, f)
            }
        }
    }

    fn fold_postorder<B>(&self, init: B, f: &mut impl FnMut(B, &T) -> B) -> B {
        match self {
            Tree::Leaf => init,
            Tree::Node(l, v, r) => {
                let acc = l.fold_postorder(init, f);
                let acc = r.fold_postorder(acc, f);
                f(acc, v)
            }
        }
    }
}

// Approach 3: Derived operations
impl Tree<i32> {
    fn to_vec_inorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.fold_inorder((), &mut |(), x| { result.push(*x); });
        result
    }

    fn sum(&self) -> i32 {
        self.fold_inorder(0, &mut |acc, x| acc + x)
    }

    fn max_val(&self) -> Option<i32> {
        self.fold_inorder(None, &mut |acc: Option<i32>, x| {
            Some(acc.map_or(*x, |a| a.max(*x)))
        })
    }

    fn all(&self, pred: impl Fn(&i32) -> bool) -> bool {
        self.fold_inorder(true, &mut |acc, x| acc && pred(x))
    }

    fn any(&self, pred: impl Fn(&i32) -> bool) -> bool {
        self.fold_inorder(false, &mut |acc, x| acc || pred(x))
    }

    fn count(&self, pred: impl Fn(&i32) -> bool) -> usize {
        self.fold_inorder(0, &mut |acc, x| if pred(x) { acc + 1 } else { acc })
    }
}

fn main() {
    let tree = Tree::node(
        Tree::node(Tree::Leaf, 1, Tree::Leaf),
        2,
        Tree::node(
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
            4,
            Tree::node(Tree::Leaf, 5, Tree::Leaf),
        ),
    );

    println!("In-order: {:?}", tree.to_vec_inorder());
    println!("Sum: {}", tree.sum());
    println!("Max: {:?}", tree.max_val());
}

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

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

    #[test]
    fn test_inorder() {
        assert_eq!(sample_tree().to_vec_inorder(), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_sum() {
        assert_eq!(sample_tree().sum(), 15);
    }

    #[test]
    fn test_max() {
        assert_eq!(sample_tree().max_val(), Some(5));
    }

    #[test]
    fn test_all() {
        assert!(sample_tree().all(|x| *x > 0));
        assert!(!sample_tree().all(|x| *x > 2));
    }

    #[test]
    fn test_any() {
        assert!(sample_tree().any(|x| *x == 3));
        assert!(!sample_tree().any(|x| *x == 99));
    }

    #[test]
    fn test_count() {
        assert_eq!(sample_tree().count(|x| x % 2 == 0), 2);
    }

    #[test]
    fn test_preorder() {
        let mut result = Vec::new();
        sample_tree().fold_preorder((), &mut |(), x| { result.push(*x); });
        assert_eq!(result, vec![2, 1, 4, 3, 5]);
    }

    #[test]
    fn test_postorder() {
        let mut result = Vec::new();
        sample_tree().fold_postorder((), &mut |(), x| { result.push(*x); });
        assert_eq!(result, vec![1, 3, 5, 4, 2]);
    }

    #[test]
    fn test_empty_tree() {
        let t = Tree::<i32>::Leaf;
        assert_eq!(t.sum(), 0);
        assert_eq!(t.max_val(), None);
    }
}

(* Example 068: Foldable for Binary Tree *)
(* Left/right fold, collect all values, various aggregations *)

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

(* Approach 1: In-order fold (left, value, right) *)
let rec fold_inorder f acc = function
  | Leaf -> acc
  | Node (l, v, r) ->
    let acc = fold_inorder f acc l in
    let acc = f acc v in
    fold_inorder f acc r

(* Approach 2: Pre-order and post-order *)
let rec fold_preorder f acc = function
  | Leaf -> acc
  | Node (l, v, r) ->
    let acc = f acc v in
    let acc = fold_preorder f acc l in
    fold_preorder f acc r

let rec fold_postorder f acc = function
  | Leaf -> acc
  | Node (l, v, r) ->
    let acc = fold_postorder f acc l in
    let acc = fold_postorder f acc r in
    f acc v

(* Approach 3: Derived operations *)
let to_list_inorder tree = List.rev (fold_inorder (fun acc x -> x :: acc) [] tree)
let sum tree = fold_inorder (+) 0 tree
let max_val tree = fold_inorder (fun acc x -> max acc x) min_int tree
let all pred tree = fold_inorder (fun acc x -> acc && pred x) true tree
let any pred tree = fold_inorder (fun acc x -> acc || pred x) false tree
let count pred tree = fold_inorder (fun acc x -> if pred x then acc + 1 else acc) 0 tree

let () =
  let tree = Node (Node (Leaf, 1, Leaf), 2, Node (Node (Leaf, 3, Leaf), 4, Node (Leaf, 5, Leaf))) in

  assert (to_list_inorder tree = [1; 2; 3; 4; 5]);
  assert (sum tree = 15);
  assert (max_val tree = 5);
  assert (all (fun x -> x > 0) tree = true);
  assert (all (fun x -> x > 2) tree = false);
  assert (any (fun x -> x = 3) tree = true);
  assert (count (fun x -> x mod 2 = 0) tree = 2);

  (* Pre-order: root first *)
  let pre = List.rev (fold_preorder (fun acc x -> x :: acc) [] tree) in
  assert (pre = [2; 1; 4; 3; 5]);

  (* Post-order: root last *)
  let post = List.rev (fold_postorder (fun acc x -> x :: acc) [] tree) in
  assert (post = [1; 3; 5; 4; 2]);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Comparison: Foldable for Binary Tree

In-Order Fold

OCaml:

🐪 Show OCaml equivalent

let rec fold_inorder f acc = function
| Leaf -> acc
| Node (l, v, r) ->
 let acc = fold_inorder f acc l in
 let acc = f acc v in
 fold_inorder f acc r

Rust:

fn fold_inorder<B>(&self, init: B, f: &mut impl FnMut(B, &T) -> B) -> B {
 match self {
     Tree::Leaf => init,
     Tree::Node(l, v, r) => {
         let acc = l.fold_inorder(init, f);
         let acc = f(acc, v);
         r.fold_inorder(acc, f)
     }
 }
}

Derived Operations