037 Intermediate GitHub

037 — Preorder Traversal Sequence

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "037 — Preorder Traversal Sequence" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Preorder traversal visits nodes in root-left-right order, producing a sequence where the root always comes before its descendants. Key difference from OCaml: 1. **String construction**: Rust uses `format!` or `String::push`. OCaml uses `^` (string concatenation) which is O(n) per call — avoid in inner loops; use `Buffer` instead.

Tutorial

The Problem

Preorder traversal visits nodes in root-left-right order, producing a sequence where the root always comes before its descendants. This ordering has a critical property: in a full binary tree (where leaves are uniquely identifiable), the preorder sequence uniquely determines the tree. Combined with the inorder sequence (from example 038), any binary tree can be reconstructed.

Preorder traversal underlies expression tree serialization (prefix notation: "+ 3 4" rather than "3 + 4"), directory tree listing (find command), syntax tree serialization in compilers, and tree copying algorithms. Depth-first search (DFS) on graphs is a generalization of preorder traversal.

🎯 Learning Outcomes

• Implement preorder traversal: visit root, then left subtree, then right subtree

• Use a dot-string encoding where . represents a leaf (self-delimiting format)

• Understand why the dot-string encoding is self-delimiting (unlike the format in #036)

• Reconstruct a tree from its preorder dot-string sequence

• Contrast preorder with inorder (root between children) and postorder (root after)

• Collect values in pre-order (root, then left subtree, then right subtree) — order used for tree serialization

• For large trees, use an explicit Vec stack instead of recursion to avoid stack overflow

Code Example

#![allow(clippy::all)]
// Preorder dot-string encoding of a tree: "." for Leaf, self-delimiting (OCaml 99 Problems, ext. of #29-40).
#[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 preorder(tree: &Tree<char>) -> String {
    match tree {
        Tree::Leaf => ".".to_string(),
        Tree::Node(c, l, r) => format!("{}{}{}", c, preorder(l), preorder(r)),
    }
}

pub fn from_preorder(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> {
    let c = chars[*pos];
    *pos += 1;
    if c == '.' {
        Tree::Leaf
    } else {
        let left = parse(chars, pos);
        let right = parse(chars, pos);
        Tree::node(c, left, right)
    }
}

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

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

    #[test]
    fn test_preorder_encoding() {
        assert_eq!(preorder(&sample()), "ab..c..");
    }

    #[test]
    fn test_from_preorder() {
        assert_eq!(from_preorder("ab..c.."), sample());
    }

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

    #[test]
    fn test_leaf_tree() {
        assert_eq!(preorder(&Tree::Leaf), ".");
        assert_eq!(from_preorder("."), Tree::Leaf);
    }
}

(* Tree Preorder *)
(* OCaml 99 Problems, extension of #29-40 *)

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 preorder = function
  | Leaf -> "."
  | Node (c, l, r) -> String.make 1 c ^ preorder l ^ preorder r

let from_preorder s =
  let pos = ref 0 in
  let rec parse () =
    let c = s.[!pos] in
    incr pos;
    if c = '.' then Leaf
    else
      let l = parse () in
      let r = parse () in
      Node (c, l, r)
  in
  parse ()

(* Tests *)
let () =
  let sample = node 'a' (node 'b' leaf leaf) (node 'c' leaf leaf) in
  assert (preorder sample = "ab..c..");
  assert (from_preorder "ab..c.." = sample);
  assert (from_preorder (preorder sample) = sample);
  assert (preorder leaf = ".");
  assert (from_preorder "." = leaf);
  print_endline "✓ OCaml tests passed"

Key Differences

String construction: Rust uses format! or String::push. OCaml uses ^ (string concatenation) which is O(n) per call — avoid in inner loops; use Buffer instead.

Self-delimiting encoding: The dot-string encoding is self-delimiting because . consumes exactly one position, and a node character consumes one position followed by two self-delimiting subtrees. No length prefix needed.

Reconstruction state: Rust passes &mut usize cursor or slices. OCaml's functional version returns (result, remaining_string) pairs — the monadic parser style.

Round-trip uniqueness: Preorder dot-string uniquely determines the tree. This is used for equality testing: two trees are equal iff their preorder dot-strings are equal.

Traversal order: Pre-order visits root → left → right. This produces the tree in "polish notation" order — useful for serialization, expression evaluation (prefix notation), and copying trees.

Stack-based vs recursive: The recursive version is straightforward but O(d) stack depth. The explicit-stack version maintains a Vec<&Tree<T>> and processes nodes iteratively — safe for deep trees in Rust (no TCO guarantee).

**extend for subtrees:** result.extend(preorder(left)); result.extend(preorder(right)) copies values. An accumulator approach (preorder_aux(tree, &mut acc)) is more efficient for large trees.

Stack-based iterative: Using a Vec<&Tree<T>> stack avoids deep recursion. Push right child first, then left, so left is processed first (LIFO stack reverses order).

OCaml Approach

OCaml's version: let rec preorder = function | Leaf -> "." | Node (c, l, r) -> String.make 1 c ^ preorder l ^ preorder r. Reconstruction: let rec of_preorder s = match s.[0] with | '.' -> (Leaf, String.sub s 1 ...) | c -> let (l, s') = of_preorder (String.sub s 1 ...) in let (r, s'') = of_preorder s' in (Node (c, l, r), s''). The function returns (tree, remaining_string).

Full Source

#![allow(clippy::all)]
// Preorder dot-string encoding of a tree: "." for Leaf, self-delimiting (OCaml 99 Problems, ext. of #29-40).
#[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 preorder(tree: &Tree<char>) -> String {
    match tree {
        Tree::Leaf => ".".to_string(),
        Tree::Node(c, l, r) => format!("{}{}{}", c, preorder(l), preorder(r)),
    }
}

pub fn from_preorder(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> {
    let c = chars[*pos];
    *pos += 1;
    if c == '.' {
        Tree::Leaf
    } else {
        let left = parse(chars, pos);
        let right = parse(chars, pos);
        Tree::node(c, left, right)
    }
}

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

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

    #[test]
    fn test_preorder_encoding() {
        assert_eq!(preorder(&sample()), "ab..c..");
    }

    #[test]
    fn test_from_preorder() {
        assert_eq!(from_preorder("ab..c.."), sample());
    }

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

    #[test]
    fn test_leaf_tree() {
        assert_eq!(preorder(&Tree::Leaf), ".");
        assert_eq!(from_preorder("."), Tree::Leaf);
    }
}

(* Tree Preorder *)
(* OCaml 99 Problems, extension of #29-40 *)

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 preorder = function
  | Leaf -> "."
  | Node (c, l, r) -> String.make 1 c ^ preorder l ^ preorder r

let from_preorder s =
  let pos = ref 0 in
  let rec parse () =
    let c = s.[!pos] in
    incr pos;
    if c = '.' then Leaf
    else
      let l = parse () in
      let r = parse () in
      Node (c, l, r)
  in
  parse ()

(* Tests *)
let () =
  let sample = node 'a' (node 'b' leaf leaf) (node 'c' leaf leaf) in
  assert (preorder sample = "ab..c..");
  assert (from_preorder "ab..c.." = sample);
  assert (from_preorder (preorder sample) = sample);
  assert (preorder leaf = ".");
  assert (from_preorder "." = 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::leaf(), Tree::leaf()), Tree::node('c', Tree::leaf(), Tree::leaf()))
    }

    #[test]
    fn test_preorder_encoding() {
        assert_eq!(preorder(&sample()), "ab..c..");
    }

    #[test]
    fn test_from_preorder() {
        assert_eq!(from_preorder("ab..c.."), sample());
    }

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

    #[test]
    fn test_leaf_tree() {
        assert_eq!(preorder(&Tree::Leaf), ".");
        assert_eq!(from_preorder("."), Tree::Leaf);
    }
}

Deep Comparison

OCaml vs Rust: Tree Preorder

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

Postorder: Write postorder(tree: &Tree<char>) -> String with left-right-root order using a similar dot-string encoding. The dot for leaves must appear after the two empty subtrees.

Tree from pre+in: Given a preorder sequence and an inorder sequence (both without dots), reconstruct the unique binary tree. This is the classic interview question.

Preorder vs BFS: Compare the preorder sequence with the BFS level-order sequence on the same tree. Draw the tree, list both sequences, and explain the structural difference.

Iterative preorder: Implement preorder_iterative<T: Clone>(tree: &Tree<T>) -> Vec<T> using an explicit Vec stack to avoid recursion — safe for arbitrarily deep trees.

Serialize via preorder: Show how preorder traversal together with the None/Some distinction uniquely serializes a binary tree. Implement both serialize (preorder with None for leaves) and deserialize (consume from iterator).

Open Source Repos

functional-rust

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

Rust