Tree to ordered list with tail recursion

Question

I am actually sitting over a hour on a problem and don´t find a solution for it. I have this data type: type 'a tree = Empty | Node of 'a * 'a tree * 'a tree

And i have to find a function which converts a given tree in a ordered list. There is also no invariant like that the left child has to be less then the right. I already found a "normal" recursion solution but not a tail recursive solution. I already thought about to build a unordered list and sort it with List.sort, but this uses a merge sort which is not tail recursive. Maybe someone has a good advice.

Thank you!

Answer 1

You mention implementing a "dirty" solution with stacks, but there really isn't necessarily anything wrong with using stacks. Using continuation passing is clean, but requires allocating larger and larger closures the deeper we have to recurse.

Using a stack works quite nicely for tree traversal. We aren't actually copying nodes, but rather just adding existing nodes to a list, and we can create those quite easily with ::.

This approach also can be adapted to work with sequences, allowing traversal of large trees to occur efficiently.

# let inorder_seq t =
    let leaf v = Node (v, Empty, Empty) in
    let rec aux t to_process () =
      match t, to_process with
      | Empty, [] -> Seq.Nil
      | Node (v, Empty, Empty), [] -> Seq.Cons (v, Seq.empty)
      | Node (v, Empty, Empty), x::xs -> Seq.Cons (v, aux x xs)
      | Empty, x::xs -> aux x xs ()
      | Node (v, l, r), _ -> aux l (leaf v :: r :: to_process) ()
    in
    aux t [];;
val inorder_seq : 'a tree -> 'a Seq.t = <fun>
# let leaf v = Node (v, Empty, Empty) in
  Node (1, Node (2, leaf 4, leaf 5), Node (3, leaf 6, leaf 7))
  |> inorder_seq
  |> List.of_seq;;
- : int list = [4; 2; 5; 1; 6; 3; 7]

Now, if I wanted to check for a value in the tree using in order traversal, I can simply leverage Seq.find.

# let leaf v = Node (v, Empty, Empty) in
  Node (1, Node (2, leaf 4, leaf 5), Node (3, leaf 6, leaf 7))
  |> inorder_seq
  |> Seq.find  @@ (=) 2;;
- : int option = Some 2

This approach also benefits that it's very easy to modify for different traversal orders. Consider pre-order traversal.

# let preorder_seq t =
    let leaf v = Node (v, Empty, Empty) in
    let rec aux t to_process () =
      match t, to_process with
      | Empty, [] -> Seq.Nil
      | Node (v, Empty, Empty), [] -> Seq.Cons (v, Seq.empty)
      | Node (v, Empty, Empty), x::xs -> Seq.Cons (v, aux x xs)
      | Empty, x::xs -> aux x xs ()
      | Node (v, l, r), _ -> aux (leaf v) (l :: r :: to_process) ()
    in
    aux t [];;
val preorder_seq : 'a tree -> 'a Seq.t = <fun>
# let leaf v = Node (v, Empty, Empty) in
  Node (1, Node (2, leaf 4, leaf 5), Node (3, leaf 6, leaf 7))
  |> preorder_seq
  |> List.of_seq;;
- : int list = [1; 2; 4; 5; 3; 6; 7]

Efficiency

Consider that for something like a balanced binary search tree, lookups are already O(log n). Such a tree with 10,000 nodes only requires at most ~13 levels of recursion. One hundred million nodes in such a tree requires approximately 27 levels of recursion. These are unlikely to pose a concern when it comes to a stack overflow, so the non-tail-recursive solution is likely ideal from an efficiency standpoint.

Answer 2

If you want to traverse the tree in order and return a list, that means our function inorder must have the type 'a tree -> 'a list.

let rec inorder t =
    match t with
      | Empty -> []
      | Node (v, l, r) -> List.append (inorder l) (v :: (inorder r)) (* ! *)

However List.append is in tail position, not inorder. Another problem is we have two calls to inorder. If we put inorder l in tail position, inorder r could not possibly be in tail position - and vice versa.

A neat way to work around this problem is continuation passing style. We take our function above and convert it into a helper function with an extra parameter for our continuation, return

(* convert to helper function, add an extra parameter *)
let rec loop t return =
    match t with
        | Empty -> ...
        | Node (v, l, r) -> ...

The continuation represents "what to do next", so instead of sending values directly out of our function, we must hand them to the continuation instead. That means for the Empty case, we'll return [] - instead of simply []

let rec loop t return =
    match t with
        | Empty -> return []
        | Node (v, l, r) -> ...

For the Node (v, l, r) case, now that we have an extra parameter we can write our own continuation that informs loop what to do next. So to construct our sorted list, we will need to loop l, then loop r (or vice versa), then we can append them. We'll write our program just like this.

let rec loop t return =
    match t with
        | Empty -> return []
        | Node (v, l, r) ->
            loop l ... (* build the left_result *)
            loop r ... (* build the right_result *)
            return (List.append left_result (v :: right_result))

In this next step, we'll fill in the actual lambda syntax for the continuations.

let rec loop t return =
    match t with
        | Empty -> return []
        | Node (v, l, r) ->
            loop l (fun left ->
            loop r (fun right ->
            return (List.append left (v :: right))))

Last, we define inorder which is a call to loop with the default continuation, identity.

let identity x =
    x

let inorder t =
    let rec loop t return =
        match t with
            | Empty -> return []
            | Node (v, l, r) ->
                loop r (fun right ->
                loop l (fun left ->
                return (List.append left (v :: right))))
    in
    loop t identity

As you can see loop r (fun right -> ...) is in tail position for the Node branch. loop l (fun left -> ...) is in tail position of the first continuation. And List.append ... is in tail position of the second continuation. Provided List.append is a tail-recursive procedure, inorder will not grow the stack.

---

Note using List.append could be a costly choice for big trees. Our function calls it once per Node. Can you think of a way to avoid it? This exercise is left for the reader.