Dive C4.02.2

Traversals — DFS & BFS

Visit the node before, between, or after its subtrees, and the same recursion gives a different order.

A traversal visits every node once. The shape is recursive, so the traversal is too — and the four orders differ only in when the node is visited relative to its two subtrees. Depth-first follows one branch to the bottom before backing up: move the node to the front, the middle, or the back of the recursion and you get pre-, in-, and post-order. Breadth-first sweeps level by level with a queue. In-order on a binary search tree comes out sorted — the property the bus's due-scan rides at the end of this dive. Every order below was produced by dotnet fsi over the seven-node tree from C4.02.1.

Walk the tree Module hub

C4.02.2 · part 1

Depth-first: pre, in, post-order

Depth-first recurses into a whole subtree before moving on. The three orders are the same two recursive calls with the node placed first, in the middle, or last. Each is a three-line function over the Tree union — a clause for Leaf and a clause for a Node.

Elixir — in-order over a tuple tree

# Elixir — depth-first, in-order
def inorder({v, l, r}), do: inorder(l) ++ [v] ++ inorder(r)
def inorder(nil), do: []

F# — the three orders (verified in FSI)

let rec preorder t =
    match t with
    | Leaf -> []
    | Node(l, v, r) -> v :: preorder l @ preorder r

let rec inorder t =
    match t with
    | Leaf -> []
    | Node(l, v, r) -> inorder l @ [v] @ inorder r

let rec postorder t =
    match t with
    | Leaf -> []
    | Node(l, v, r) -> postorder l @ postorder r @ [v]

// preorder  tree -> [12; 8; 5; 10; 30; 20; 42]
// inorder   tree -> [5; 8; 10; 12; 20; 30; 42]   sorted, on a BST
// postorder tree -> [5; 10; 8; 20; 42; 30; 12]

preorder: node, then left, then right — the order to copy a tree or print it as a prefix expression.
inorder: left, then node, then right — on a binary search tree, the values come out sorted.
postorder: left, then right, then node — the order to fold a tree from the leaves up.

Walk the tree, four ways

Select an order. The diagram highlights the nodes in the order the F# function emits them; the readout shows the full sequence the function returns over the seven-node tree, every value produced by dotnet fsi. The first three are depth-first; level is the breadth-first sweep developed below.

The order · select one

let rec preorder t =
    match t with
    | Leaf -> []
    | Node(l, v, r) -> v :: preorder l @ preorder r
// preorder tree -> [12; 8; 5; 10; 30; 20; 42]

pre-order · visits the node first, then its left subtree, then its right — the order to copy a tree. Result: [12; 8; 5; 10; 30; 20; 42].

sequence: 12 · 8 · 5 · 10 · 30 · 20 · 42

Without JavaScript, the four orders over this tree are: pre [12; 8; 5; 10; 30; 20; 42] · in [5; 8; 10; 12; 20; 30; 42] · post [5; 10; 8; 20; 42; 30; 12] · level [12; 8; 30; 5; 10; 20; 42].

The recursion is the same three subtrees every time. Move the node — front, middle, or back — and the order changes; in-order on a search tree is the one that comes out sorted.

C4.02.2 · part 2

Breadth-first: level-order with a queue

Breadth-first sweeps level by level. A queue turns the recursion inside out: instead of going deep and returning, keep a running line of nodes to visit, oldest first. Take the front node, record its value, push its children to the back. A list used as a queue keeps the example honest; production code reaches for a real Queue for O(1) enqueue.

let levelOrder root =
    let rec walk queue acc =
        match queue with
        | [] -> List.rev acc
        | Leaf :: rest -> walk rest acc
        | Node(l, v, r) :: rest -> walk (rest @ [l; r]) (v :: acc)
    walk [root] []

// levelOrder tree -> [12; 8; 30; 5; 10; 20; 42]

Depth-first

Recurse into a whole subtree before the next — the call stack holds where to return.

Breadth-first

A FIFO queue holds what to visit next; the root, then its children, then theirs — level by level.

Cost is the same either way: O(n), every node visited once. The difference is the working memory — a stack of ancestors for depth, a queue of the next level for breadth.

C4.02.2 · the bus

EchoMQ in F# — promote walks the schedule in order

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

EchoMQ in F#

The F# EchoMQ does not walk its schedule node by node, but it does something the same in kind — an in-order selection over the tree. EchoMQ.Store.promote moves every due job out of the schedule and back to pending. It filters the Schedule map for entries whose due-at time has passed, then folds them across.

// echo_fs/EchoMQ/Store.fs — promote: the in-order due selection
let promote (now: int64) (st: QueueState) : QueueState * int =
    let due =
        st.Schedule
        |> Map.filter (fun _ dueAt -> dueAt <= now)
        |> Map.toList
        |> List.map fst
    // ... fold each due id back to Pending ...

Map.filter and Map.toList walk the schedule in key order — exactly the in-order traversal of this dive, over a Map that is a balanced search tree. A claim, separately, takes the front of the pending set with Set.minElement — also an in-order extraction, the oldest mint first.

Today: the promote pump runs the in-order selection over the in-memory Store, built and tested. Coming soon: the Valkey transport (EchoMQ.Connector) runs the same selection against the durable store.

Where this leads

Every order costs O(n); the in-order one sorts a search tree, and the bus rides that sorting to find due jobs and the oldest mint. The next dive asks what keeps those walks cheap — why a balanced tree turns the descent into O(log n), how it decays when balance is lost, and how F#'s own Map and Set stay balanced for you.

↑ C4.02 · Trees & traversals ← C4.02.1 · Binary trees C4.02.3 · Balancing →