Loopless function algorithm for binary search tree in-order traversal

Question

According to Pearls of Functional Algorithm Design, loopless function is

Imagine a program for generating combinatorial patterns of some kind, patterns such as the subsequences or permutations of a list.

Suppose that each pattern is obtained from its predecessor by a single transition. For subsequences a transition i could mean insert or delete the element at position i. For permutations a transition i could mean “swap the item in position i with the one in position i − 1.

An algorithm for generating all patterns is called loopless if the first transition is produced in linear time and each subsequent transition in constant time. Note that it is the transitions that are produced in constant time, not the patterns; writing out a pattern is not usually possible in constant time.

---

For example, we can have our binary search tree pre-order traversal like this:

type 'a bst = Empty | Node of 'a bst * 'a * 'a bst

let rec preorder = function
  | Empty -> []
  | Node (l, x, r) -> x::preorder l @ preorder r

In order to make the pre-order traversal loopless, we need to prepare the first transition:

let prepare t = [t]

Then we define the step_f which is the function for the subsequent transition:

let step_f = function
  | [] -> None
  | t::tl -> 
    match t with
      | Empty -> failwith "wrong"
      | Node (Empty, x, Empty) -> Some (x, tl)
      | Node (Empty, x, c) | Node (c, x, Empty) -> Some (x, c::tl)
      | Node (l, x, r) -> Some (x, l::r::tl)

Basically, step_f take out one element directly and prepare for the next transition which can be used in next step.

We can have a standard unfold function which wire the whole process

let rec unfold a =
  match step_f a with
    | None -> []
    | Some (b, a') -> b::unfold a'

let _ = unfold (prepare bst)

This loopless thing can naturally be used to construct lazy functions, etc.

---

My question here is how to design a loopless function for bst in-order traversal?

Note that the prepare process costs at most O(n) and step process costs O(1).

Answer 1

We can easily generate the in-order traversal in O(n) time, so one approach would be:

• Generate the in-order traversal and store it in a list

• Loop through the list, outputting each element

This takes O(n) to get to the first one, then O(1) for each one after.

---

O(n) in-order traversal can be done with something like this (in pseudo-code): (from Wikipedia)

inorder(node)
  if node == null
    return
  inorder(node.left)
  store(node)
  inorder(node.right)

---

I don't really know OCaml, but I hope the fundamental idea still holds.