🎬 Pattern Matching Exhaustive match, destructuring, guards, let-else — compiler-verified branching.

📝 Text version (for readers / accessibility)

• match is exhaustive — the compiler ensures every variant is handled

• Destructuring extracts fields from structs, tuples, and enums in one step

• Guards (if conditions) add extra logic to match arms

• if let and let-else provide concise single-pattern matching

• Nested patterns and @ bindings handle complex data shapes elegantly

036: Tree String

Difficulty: ⭐⭐ Level: Foundations Serialize a binary tree to a string like `"a(b(d,e),c(,f))"` and parse it back.

The Problem This Solves

Data structures live in memory. But memory is ephemeral — you need to save a tree to disk, send it over a network, or embed it in a config file. That requires serialization: converting the in-memory structure to a portable string. This example implements a human-readable format: `a(left,right)`. A leaf node with no children is just its character. A node with children wraps them in parentheses: `a(b,c)`. An empty subtree is an empty string. Round-tripping — serialize then parse and get back the exact same tree — is the key test. Real-world relevance: Newick format (phylogenetic trees in biology), S-expressions in Lisp, and many configuration formats use exactly this parenthetical nesting approach.

The Intuition

Serialization and parsing are mirror images. Serialization descends the tree and builds up a string. Parsing reads left-to-right and reconstructs the tree. Serialize:

`Leaf` → `""` (empty string)
`Node(l, 'a', r)` where both children are leaves → `"a"`
Otherwise → `"a(serialize(l),serialize(r))"`

Parse (recursive descent parser):

Read a character — that's the current node's value.
If the next char is `(`, parse left child, expect `,`, parse right child, expect `)`.
If no `(`, it's a leaf node.
If we're at `,` or `)` or end of string, return `Leaf`.

This is a classic recursive descent parser — one of the most important patterns in programming language implementation. Every JSON parser, every YAML parser, every SQL parser is built on this idea.

How It Works in Rust

fn tree_to_string(tree: &Tree) -> String {
 match tree {
     Tree::Leaf => String::new(),  // empty = empty string

     Tree::Node(l, v, r) => match (l.as_ref(), r.as_ref()) {
         // Leaf node — just the character
         (Tree::Leaf, Tree::Leaf) => v.to_string(),

         // Internal node — wrap children in parens
         _ => format!("{}({},{})", v, tree_to_string(l), tree_to_string(r)),
     },
 }
}

fn parse(chars: &[char], pos: &mut usize) -> Tree {
 if *pos >= chars.len()
     || chars[*pos] == ','
     || chars[*pos] == ')' {
     return Tree::leaf();  // end of input or closing delimiter → Leaf
 }

 let v = chars[*pos];
 *pos += 1;

 if *pos < chars.len() && chars[*pos] == '(' {
     *pos += 1;  // skip '('
     let left = parse(chars, pos);
     // pos now points at ','
     *pos += 1;  // skip ','
     let right = parse(chars, pos);
     // pos now points at ')'
     *pos += 1;  // skip ')'
     Tree::node(left, v, right)
 } else {
     Tree::node(Tree::leaf(), v, Tree::leaf())  // no parens → leaf node
 }
}

Example round-trip:

Tree → "a(b(d,e),c(,f))" → Tree (identical)

The `&mut usize` position pointer advances as the parser consumes input — another example of threading mutable state through recursion.

What This Unlocks

Serialization patterns: the same serialize/parse symmetry applies to JSON, XML, and custom formats.
Recursive descent parsing: this mini-parser is the foundation of every hand-written language parser.
Config files: embed tree-structured data in plain text without a library.

Key Differences

Concept	OCaml	Rust
String building	`String.concat` / `Printf.sprintf`	`format!()` macro
Mutable position in parser	`ref int` or return pair	`&mut usize` position pointer
Character access	`String.get`	`chars().collect::<Vec<_>>()` then index
Empty string	`""`	`String::new()`

// Tree String — 99 Problems #36
// Convert a binary tree to/from a string representation.
// Format: "a(b(d,e),c(,f))" — Node(left,right), empty = ""

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

impl Tree {
    fn leaf() -> Self { Tree::Leaf }
    fn node(l: Tree, v: char, r: Tree) -> Self {
        Tree::Node(Box::new(l), v, Box::new(r))
    }
}

/// Convert tree to string.
fn tree_to_string(tree: &Tree) -> String {
    match tree {
        Tree::Leaf => String::new(),
        Tree::Node(l, v, r) => {
            match (l.as_ref(), r.as_ref()) {
                (Tree::Leaf, Tree::Leaf) => v.to_string(),
                _ => format!("{}({},{})", v, tree_to_string(l), tree_to_string(r)),
            }
        }
    }
}

/// Parse a tree string back to Tree.
fn string_to_tree(s: &str) -> Tree {
    parse(&s.chars().collect::<Vec<_>>(), &mut 0)
}

fn parse(chars: &[char], pos: &mut usize) -> Tree {
    if *pos >= chars.len() || chars[*pos] == ',' || chars[*pos] == ')' {
        return Tree::leaf();
    }
    let v = chars[*pos];
    *pos += 1;

    if *pos < chars.len() && chars[*pos] == '(' {
        *pos += 1; // skip '('
        let left = parse(chars, pos);
        assert_eq!(chars[*pos], ',');
        *pos += 1; // skip ','
        let right = parse(chars, pos);
        assert_eq!(chars[*pos], ')');
        *pos += 1; // skip ')'
        Tree::node(left, v, right)
    } else {
        Tree::node(Tree::leaf(), v, Tree::leaf())
    }
}

fn sample_tree() -> Tree {
    //      a
    //     / \
    //    b   c
    //   / \   \
    //  d   e   f
    Tree::node(
        Tree::node(
            Tree::node(Tree::leaf(), 'd', Tree::leaf()),
            'b',
            Tree::node(Tree::leaf(), 'e', Tree::leaf()),
        ),
        'a',
        Tree::node(Tree::leaf(), 'c', Tree::node(Tree::leaf(), 'f', Tree::leaf())),
    )
}

fn main() {
    let t = sample_tree();
    let s = tree_to_string(&t);
    println!("Tree → String: {}", s);

    let parsed = string_to_tree(&s);
    println!("String → Tree: {:?}", parsed);
    println!("Round-trip OK: {}", t == parsed);

    println!("Single 'x':  {}", tree_to_string(&Tree::node(Tree::leaf(), 'x', Tree::leaf())));
    println!("Empty: '{}'", tree_to_string(&Tree::leaf()));
}

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

    #[test]
    fn test_leaf_to_string() {
        assert_eq!(tree_to_string(&Tree::leaf()), "");
    }

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

    #[test]
    fn test_round_trip() {
        let t = sample_tree();
        let s = tree_to_string(&t);
        assert_eq!(string_to_tree(&s), t);
    }

    #[test]
    fn test_parse_single() {
        let t = string_to_tree("x");
        assert_eq!(t, Tree::node(Tree::leaf(), 'x', Tree::leaf()));
    }
}

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

(* Implementation for example 36 *)

(* Tests *)
let () =
  (* Add tests *)
  print_endline "✓ OCaml tests passed"