ExamplesBy LevelBy TopicLearning Paths
036 Intermediate
← 035037 →

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)]
// Placeholder — pending conversion

    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)]
// Placeholder — pending conversion

    Deep Comparison

    OCaml vs Rust: Tree String

    Overview

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

    Key Differences

    AspectOCamlRust
    Type systemHindley-MilnerOwnership + traits
    MemoryGCZero-cost abstractions
    MutabilityExplicit refmut keyword
    Error handlingOption/ResultResult<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