038 Intermediate GitHub

038 — Inorder Traversal Sequence

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "038 — Inorder Traversal Sequence" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Inorder traversal visits nodes in left-subtree, root, right-subtree order. Key difference from OCaml: 1. **BST sorted output**: Rust's `BTreeMap` uses inorder traversal internally to implement `iter()` — the elements come out sorted. Understanding inorder traversal explains why BTree iteration is sorted.

Tutorial

The Problem

Inorder traversal visits nodes in left-subtree, root, right-subtree order. For a binary search tree (BST), inorder traversal produces a sorted sequence — this is the key property that makes BSTs useful for range queries. For expression trees, inorder with parentheses produces the standard algebraic notation "3 + 4".

Unlike preorder, inorder alone does not uniquely determine a binary tree (many trees can produce the same inorder sequence). However, combining preorder + inorder uniquely determines any binary tree. This pair is used in tree serialization protocols and in algorithms that reconstruct trees from traversal data.

🎯 Learning Outcomes

• Implement inorder traversal: left subtree, then root, then right subtree

• Understand that inorder of a BST produces a sorted sequence

• Use inorder + preorder to reconstruct a unique binary tree

• Contrast the three traversal orders: pre, in, post

• Recognize inorder as the "natural" reading order for mathematical expressions

• Collect values in in-order (left subtree, then root, then right subtree) — sorted order for BSTs

• Use in-order traversal to validate a BST: the output sequence must be strictly increasing

Code Example

#![allow(clippy::all)]
// Inorder traversal: left, root, right (OCaml 99 Problems, ext. of #29-40).
// For a BST, inorder produces a sorted sequence.
#[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 inorder<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(v, l, r) => {
            let mut result = inorder(l);
            result.push(v.clone());
            result.extend(inorder(r));
            result
        }
    }
}

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

    #[test]
    fn test_inorder_general_tree() {
        let t = Tree::node('a', Tree::node('b', Tree::leaf(), Tree::leaf()), Tree::node('c', Tree::leaf(), Tree::leaf()));
        assert_eq!(inorder(&t), vec!['b', 'a', 'c']);
    }

    #[test]
    fn test_inorder_of_bst_is_sorted() {
        // BST:      5
        //          / \
        //         3   8
        //        / \
        //       1   4
        let bst = Tree::node(
            5,
            Tree::node(3, Tree::node(1, Tree::leaf(), Tree::leaf()), Tree::node(4, Tree::leaf(), Tree::leaf())),
            Tree::node(8, Tree::leaf(), Tree::leaf()),
        );
        assert_eq!(inorder(&bst), vec![1, 3, 4, 5, 8]);
    }

    #[test]
    fn test_inorder_empty_tree() {
        let empty: Vec<i32> = vec![];
        assert_eq!(inorder::<i32>(&Tree::leaf()), empty);
    }
}

(* Tree Inorder *)
(* 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 inorder = function
  | Leaf -> []
  | Node (x, l, r) -> inorder l @ [x] @ inorder r

(* Tests *)
let () =
  let t = node 'a' (node 'b' leaf leaf) (node 'c' leaf leaf) in
  assert (inorder t = ['b'; 'a'; 'c']);

  let bst = node 5 (node 3 (node 1 leaf leaf) (node 4 leaf leaf)) (node 8 leaf leaf) in
  assert (inorder bst = [1; 3; 4; 5; 8]);

  assert (inorder leaf = []);
  print_endline "✓ OCaml tests passed"

Key Differences

BST sorted output: Rust's BTreeMap uses inorder traversal internally to implement iter() — the elements come out sorted. Understanding inorder traversal explains why BTree iteration is sorted.

Non-uniqueness: Inorder sequence alone does not uniquely determine a tree. The trees Node(1, Node(2, Leaf, Leaf), Leaf) and Node(2, Leaf, Node(1, Leaf, Leaf)) both have inorder [1, 2]. Always use preorder+inorder or inorder+postorder pairs for reconstruction.

Accumulator style: Both languages benefit from threading an accumulator through inorder traversal to avoid repeated list concatenation. The accumulator collects in reverse order; reverse at the end.

In-place: For arrays, inorder traversal can be done iteratively using an explicit stack, avoiding O(log n) recursion overhead.

Traversal order: In-order visits left → root → right. For a binary search tree, this produces elements in sorted order — the defining property of BSTs. In-order traversal is the basis for BST iteration.

Application: The in-order sequence of a BST is the sorted sequence of keys. Reconstructing a tree from its in-order + pre-order sequences uniquely determines the tree structure.

Comparison with pre-order: Pre-order is for serialization/copying; in-order is for BST validation and sorted iteration; post-order is for deletion (visit children before parent) and expression evaluation.

Iterative inorder complexity: The iterative inorder algorithm using a stack is more complex than iterative pre/post-order because you must push the node itself to process after its left subtree.

OCaml Approach

OCaml's version: let rec inorder = function | Leaf -> [] | Node (x, l, r) -> inorder l @ [x] @ inorder r. For a BST where the tree maintains sorted order, this returns values in ascending order. The string version: inorder_str l ^ String.make 1 x ^ inorder_str r. The @ concatenation is O(|left|) — use accumulator style for efficiency.

Full Source

#![allow(clippy::all)]
// Inorder traversal: left, root, right (OCaml 99 Problems, ext. of #29-40).
// For a BST, inorder produces a sorted sequence.
#[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 inorder<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(v, l, r) => {
            let mut result = inorder(l);
            result.push(v.clone());
            result.extend(inorder(r));
            result
        }
    }
}

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

    #[test]
    fn test_inorder_general_tree() {
        let t = Tree::node('a', Tree::node('b', Tree::leaf(), Tree::leaf()), Tree::node('c', Tree::leaf(), Tree::leaf()));
        assert_eq!(inorder(&t), vec!['b', 'a', 'c']);
    }

    #[test]
    fn test_inorder_of_bst_is_sorted() {
        // BST:      5
        //          / \
        //         3   8
        //        / \
        //       1   4
        let bst = Tree::node(
            5,
            Tree::node(3, Tree::node(1, Tree::leaf(), Tree::leaf()), Tree::node(4, Tree::leaf(), Tree::leaf())),
            Tree::node(8, Tree::leaf(), Tree::leaf()),
        );
        assert_eq!(inorder(&bst), vec![1, 3, 4, 5, 8]);
    }

    #[test]
    fn test_inorder_empty_tree() {
        let empty: Vec<i32> = vec![];
        assert_eq!(inorder::<i32>(&Tree::leaf()), empty);
    }
}

(* Tree Inorder *)
(* 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 inorder = function
  | Leaf -> []
  | Node (x, l, r) -> inorder l @ [x] @ inorder r

(* Tests *)
let () =
  let t = node 'a' (node 'b' leaf leaf) (node 'c' leaf leaf) in
  assert (inorder t = ['b'; 'a'; 'c']);

  let bst = node 5 (node 3 (node 1 leaf leaf) (node 4 leaf leaf)) (node 8 leaf leaf) in
  assert (inorder bst = [1; 3; 4; 5; 8]);

  assert (inorder leaf = []);
  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_inorder_general_tree() {
        let t = Tree::node('a', Tree::node('b', Tree::leaf(), Tree::leaf()), Tree::node('c', Tree::leaf(), Tree::leaf()));
        assert_eq!(inorder(&t), vec!['b', 'a', 'c']);
    }

    #[test]
    fn test_inorder_of_bst_is_sorted() {
        // BST:      5
        //          / \
        //         3   8
        //        / \
        //       1   4
        let bst = Tree::node(
            5,
            Tree::node(3, Tree::node(1, Tree::leaf(), Tree::leaf()), Tree::node(4, Tree::leaf(), Tree::leaf())),
            Tree::node(8, Tree::leaf(), Tree::leaf()),
        );
        assert_eq!(inorder(&bst), vec![1, 3, 4, 5, 8]);
    }

    #[test]
    fn test_inorder_empty_tree() {
        let empty: Vec<i32> = vec![];
        assert_eq!(inorder::<i32>(&Tree::leaf()), empty);
    }
}

Deep Comparison

OCaml vs Rust: Tree Inorder

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

BST sorted check: Write is_bst(tree: &Tree<i32>) -> bool using inorder traversal: the tree is a BST iff its inorder sequence is strictly increasing.

Tree from in+post: Given inorder and postorder sequences, reconstruct the unique binary tree. The last element of postorder is the root; find it in inorder to determine left/right subtree sizes.

Threaded tree: Research threaded binary trees, where Leaf pointers are replaced with pointers to the inorder predecessor/successor. This enables O(1) inorder step without recursion.

Iterative inorder: Implement inorder_iterative<T: Clone>(tree: &Tree<T>) -> Vec<T> using an explicit stack — this is more complex than pre/post-order because you need to process the left subtree before the root.

BST validation: Using in-order traversal, implement is_bst<T: Ord + Clone>(tree: &Tree<T>) -> bool — a BST's in-order traversal must be strictly increasing.

Open Source Repos

functional-rust

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

Rust