036 Intermediate GitHub

036 — Represent a Binary Tree as a String

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "036 — Represent a Binary Tree as a String" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Serializing a binary tree to a string and back (OCaml 99 Problems #36) is a fundamental serialization problem. Key difference from OCaml: 1. **String building**: Rust builds strings with `format!` macro or `String::push_str`. OCaml uses `Printf.sprintf` or `Buffer`. Both are efficient when used correctly.

Tutorial

The Problem

Serializing a binary tree to a string and back (OCaml 99 Problems #36) is a fundamental serialization problem. The format: "a(b(d,e),c(,f))" represents a tree where a is the root, with left child b (which has children d and e) and right child c (which has only right child f). Commas separate children; empty positions are left blank.

Tree serialization appears everywhere: JSON serialization of nested objects, XML document trees, S-expressions in Lisp (the most direct ancestor of this format), and protocol buffers. The round-trip invariant parse(serialize(t)) == t is the key correctness criterion.

🎯 Learning Outcomes

• Serialize a Tree<char> to a string representation

• Parse the string back to a tree (recursive descent parsing)

• Use String::with_capacity and write! for efficient string building

• Implement a simple recursive descent parser with an index/cursor

• Verify the round-trip invariant: from_str(to_str(t)) == t

• Serialize a tree to "x(left,right)" format recursively, with empty string for Leaf

• Implement fmt::Display for Tree<char> to use format! and to_string() on trees

Code Example

#![allow(clippy::all)]
// Serialize a Tree<char> to "x(left,right)" format and parse it back (OCaml 99 Problems #36).
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn leaf() -> Self {
        Tree::Leaf
    }

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

pub fn to_string(tree: &Tree<char>) -> String {
    match tree {
        Tree::Leaf => String::new(),
        Tree::Node(c, l, r) => {
            let ls = to_string(l);
            let rs = to_string(r);
            if ls.is_empty() && rs.is_empty() {
                c.to_string()
            } else {
                format!("{}({},{})", c, ls, rs)
            }
        }
    }
}

pub fn from_str(s: &str) -> Tree<char> {
    let chars: Vec<char> = s.chars().collect();
    let mut pos = 0;
    parse(&chars, &mut pos)
}

fn parse(chars: &[char], pos: &mut usize) -> Tree<char> {
    if *pos >= chars.len() || chars[*pos] == ',' || chars[*pos] == ')' {
        return Tree::Leaf;
    }
    let c = chars[*pos];
    *pos += 1;
    if *pos < chars.len() && chars[*pos] == '(' {
        *pos += 1; // consume '('
        let left = parse(chars, pos);
        *pos += 1; // consume ','
        let right = parse(chars, pos);
        *pos += 1; // consume ')'
        Tree::node(c, left, right)
    } else {
        Tree::node(c, Tree::Leaf, Tree::Leaf)
    }
}

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

    fn sample() -> Tree<char> {
        Tree::node(
            'a',
            Tree::node('b', Tree::node('d', Tree::leaf(), Tree::leaf()), Tree::node('e', Tree::leaf(), Tree::leaf())),
            Tree::node('c', Tree::leaf(), Tree::node('f', Tree::leaf(), Tree::leaf())),
        )
    }

    #[test]
    fn test_to_string() {
        assert_eq!(to_string(&sample()), "a(b(d,e),c(,f))");
    }

    #[test]
    fn test_from_str() {
        assert_eq!(from_str("a(b(d,e),c(,f))"), sample());
    }

    #[test]
    fn test_round_trip() {
        assert_eq!(from_str(&to_string(&sample())), sample());
    }

    #[test]
    fn test_single_leaf_node() {
        let t = Tree::node('x', Tree::leaf(), Tree::leaf());
        assert_eq!(to_string(&t), "x");
        assert_eq!(from_str("x"), t);
    }

    #[test]
    fn test_empty_tree() {
        assert_eq!(to_string(&Tree::Leaf), "");
        assert_eq!(from_str(""), Tree::Leaf);
    }
}

(* Tree String *)
(* OCaml 99 Problems #36 *)

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

let node x l r = Node (x, l, r)
let leaf = Leaf

let rec to_string = function
  | Leaf -> ""
  | Node (c, l, r) ->
    let ls = to_string l and rs = to_string r in
    if ls = "" && rs = "" then String.make 1 c
    else Printf.sprintf "%c(%s,%s)" c ls rs

let from_string s =
  let n = String.length s in
  let rec parse pos =
    if pos >= n || s.[pos] = ',' || s.[pos] = ')' then (Leaf, pos)
    else
      let c = s.[pos] in
      let pos = pos + 1 in
      if pos < n && s.[pos] = '(' then
        let pos = pos + 1 in
        let left, pos = parse pos in
        let pos = pos + 1 in
        let right, pos = parse pos in
        let pos = pos + 1 in
        (Node (c, left, right), pos)
      else (Node (c, Leaf, Leaf), pos)
  in
  fst (parse 0)

(* Tests *)
let () =
  let sample =
    node 'a'
      (node 'b' (node 'd' leaf leaf) (node 'e' leaf leaf))
      (node 'c' leaf (node 'f' leaf leaf))
  in
  assert (to_string sample = "a(b(d,e),c(,f))");
  assert (from_string "a(b(d,e),c(,f))" = sample);
  assert (from_string (to_string sample) = sample);
  let single = node 'x' leaf leaf in
  assert (to_string single = "x");
  assert (from_string "x" = single);
  assert (to_string leaf = "");
  assert (from_string "" = leaf);
  print_endline "✓ OCaml tests passed"

Key Differences

String building: Rust builds strings with format! macro or String::push_str. OCaml uses Printf.sprintf or Buffer. Both are efficient when used correctly.

Parser state: Rust passes &mut usize as a position cursor. OCaml can use a mutable reference or return (tree, remaining_string) from each parser function.

Error handling: Rust's parser should return Result<Tree<char>, String>. OCaml uses exceptions (failwith "parse error") in imperative code or option/result in functional style.

Leaf representation: Empty string "" for Leaf makes the format non-self-delimiting. The (,) markers tell the parser where subtrees begin and end.

String representation: The node string format is "x(left,right)" where x is the node label, and leaf is empty string "". This is the canonical OCaml 99 Problems tree string format.

Recursive string building: Both implementations build the string recursively: base case (leaf = ""), recursive case (format the node value and append subtrees). String concatenation in Rust is via format! — not as efficient as a String builder for deep trees.

**fmt::Display:** Implementing Display for Tree<T> where T: Display is the idiomatic Rust way to convert a tree to a string. OCaml uses Printf.sprintf or string concatenation.

**Buffer for performance:** Building strings via format! concatenation is O(n^2) for deep trees. Use String::with_capacity or a Write trait implementation for O(n) serialization.

OCaml Approach

OCaml's version: let rec to_string = function | Leaf -> "" | Node (c, l, r) -> let ls = to_string l and rs = to_string r in if ls = "" && rs = "" then String.make 1 c else Printf.sprintf "%c(%s,%s)" c ls rs. The parser: consume a character, then if the next character is (, recursively parse left and right with comma between, then consume ).

Full Source

#![allow(clippy::all)]
// Serialize a Tree<char> to "x(left,right)" format and parse it back (OCaml 99 Problems #36).
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn leaf() -> Self {
        Tree::Leaf
    }

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

pub fn to_string(tree: &Tree<char>) -> String {
    match tree {
        Tree::Leaf => String::new(),
        Tree::Node(c, l, r) => {
            let ls = to_string(l);
            let rs = to_string(r);
            if ls.is_empty() && rs.is_empty() {
                c.to_string()
            } else {
                format!("{}({},{})", c, ls, rs)
            }
        }
    }
}

pub fn from_str(s: &str) -> Tree<char> {
    let chars: Vec<char> = s.chars().collect();
    let mut pos = 0;
    parse(&chars, &mut pos)
}

fn parse(chars: &[char], pos: &mut usize) -> Tree<char> {
    if *pos >= chars.len() || chars[*pos] == ',' || chars[*pos] == ')' {
        return Tree::Leaf;
    }
    let c = chars[*pos];
    *pos += 1;
    if *pos < chars.len() && chars[*pos] == '(' {
        *pos += 1; // consume '('
        let left = parse(chars, pos);
        *pos += 1; // consume ','
        let right = parse(chars, pos);
        *pos += 1; // consume ')'
        Tree::node(c, left, right)
    } else {
        Tree::node(c, Tree::Leaf, Tree::Leaf)
    }
}

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

    fn sample() -> Tree<char> {
        Tree::node(
            'a',
            Tree::node('b', Tree::node('d', Tree::leaf(), Tree::leaf()), Tree::node('e', Tree::leaf(), Tree::leaf())),
            Tree::node('c', Tree::leaf(), Tree::node('f', Tree::leaf(), Tree::leaf())),
        )
    }

    #[test]
    fn test_to_string() {
        assert_eq!(to_string(&sample()), "a(b(d,e),c(,f))");
    }

    #[test]
    fn test_from_str() {
        assert_eq!(from_str("a(b(d,e),c(,f))"), sample());
    }

    #[test]
    fn test_round_trip() {
        assert_eq!(from_str(&to_string(&sample())), sample());
    }

    #[test]
    fn test_single_leaf_node() {
        let t = Tree::node('x', Tree::leaf(), Tree::leaf());
        assert_eq!(to_string(&t), "x");
        assert_eq!(from_str("x"), t);
    }

    #[test]
    fn test_empty_tree() {
        assert_eq!(to_string(&Tree::Leaf), "");
        assert_eq!(from_str(""), Tree::Leaf);
    }
}

(* Tree String *)
(* OCaml 99 Problems #36 *)

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

let node x l r = Node (x, l, r)
let leaf = Leaf

let rec to_string = function
  | Leaf -> ""
  | Node (c, l, r) ->
    let ls = to_string l and rs = to_string r in
    if ls = "" && rs = "" then String.make 1 c
    else Printf.sprintf "%c(%s,%s)" c ls rs

let from_string s =
  let n = String.length s in
  let rec parse pos =
    if pos >= n || s.[pos] = ',' || s.[pos] = ')' then (Leaf, pos)
    else
      let c = s.[pos] in
      let pos = pos + 1 in
      if pos < n && s.[pos] = '(' then
        let pos = pos + 1 in
        let left, pos = parse pos in
        let pos = pos + 1 in
        let right, pos = parse pos in
        let pos = pos + 1 in
        (Node (c, left, right), pos)
      else (Node (c, Leaf, Leaf), pos)
  in
  fst (parse 0)

(* Tests *)
let () =
  let sample =
    node 'a'
      (node 'b' (node 'd' leaf leaf) (node 'e' leaf leaf))
      (node 'c' leaf (node 'f' leaf leaf))
  in
  assert (to_string sample = "a(b(d,e),c(,f))");
  assert (from_string "a(b(d,e),c(,f))" = sample);
  assert (from_string (to_string sample) = sample);
  let single = node 'x' leaf leaf in
  assert (to_string single = "x");
  assert (from_string "x" = single);
  assert (to_string leaf = "");
  assert (from_string "" = leaf);
  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

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

    fn sample() -> Tree<char> {
        Tree::node(
            'a',
            Tree::node('b', Tree::node('d', Tree::leaf(), Tree::leaf()), Tree::node('e', Tree::leaf(), Tree::leaf())),
            Tree::node('c', Tree::leaf(), Tree::node('f', Tree::leaf(), Tree::leaf())),
        )
    }

    #[test]
    fn test_to_string() {
        assert_eq!(to_string(&sample()), "a(b(d,e),c(,f))");
    }

    #[test]
    fn test_from_str() {
        assert_eq!(from_str("a(b(d,e),c(,f))"), sample());
    }

    #[test]
    fn test_round_trip() {
        assert_eq!(from_str(&to_string(&sample())), sample());
    }

    #[test]
    fn test_single_leaf_node() {
        let t = Tree::node('x', Tree::leaf(), Tree::leaf());
        assert_eq!(to_string(&t), "x");
        assert_eq!(from_str("x"), t);
    }

    #[test]
    fn test_empty_tree() {
        assert_eq!(to_string(&Tree::Leaf), "");
        assert_eq!(from_str(""), Tree::Leaf);
    }
}

Deep Comparison

OCaml vs Rust: Tree String

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Generic tree string: Generalize to Tree<T> where T implements Display and FromStr. The format becomes "{value}({left},{right})" with any displayable value.

S-expression format: Implement a Lisp-style format: "(a (b d e) (c () f))" where () represents a leaf. This is self-delimiting and easier to parse.

JSON format: Serialize the tree as JSON: {"value": "a", "left": {...}, "right": null}. Use serde_json for serialization and deserialization.

Round-trip test: Implement both tree_to_string and tree_from_string (parser from example 040) and write a property test verifying parse(serialize(t)) == t for all trees.

JSON serialization: Implement tree_to_json<T: Serialize>(tree: &Tree<T>) -> String using the serde_json crate — a more practical serialization format than dotstring.

Open Source Repos

functional-rust

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

Rust