038 Intermediate

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

(* Tree Inorder *)
(* OCaml 99 Problems #38 *)

(* Implementation for example 38 *)

(* Tests *)
let () =
  (* Add tests *)
  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)]
// Placeholder — pending conversion

(* Tree Inorder *)
(* OCaml 99 Problems #38 *)

(* Implementation for example 38 *)

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

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