How to write iterative inorder traversal for BST in OCaml

Question

It is easy enough to write recursive inorder traversal in OCaml, but how to write iterative one? with for loop or while?

Answer 1

Here's another take on iterative in-order traversals:

type 'a node = {mutable data: 'a;
                mutable left : 'a node option;
                mutable right: 'a node option; }

let new_node data = {data; left = None; right = None;}

let insert tree new_data =
  let module Wrapper = struct exception Stop_loop end in
  let iter = ref tree in
  try
    while true do
      if new_data < !iter.data
      then match !iter.left with
        | None ->
          !iter.left <- Some (new_node new_data);
          raise Wrapper.Stop_loop
        | Some left_tree -> iter := left_tree
      else if new_data > !iter.data
      then match !iter.right with
        | None ->
          !iter.right <- Some (new_node new_data);
          raise Wrapper.Stop_loop
        | Some right_tree -> iter := right_tree
    done
  with Wrapper.Stop_loop -> ()

let in_order_traversal tree =
  let module W = struct exception Stop_loop end in
  let visited_stack = Stack.create () in
  let iter_node = ref (Some tree) in
  try while true do
      (* Inner loop, we keep trying to go left *)
      (try while true do
           match !iter_node with
           | None -> raise W.Stop_loop
           | Some left ->
             Stack.push left visited_stack;
             iter_node := left.left
         done;
       with W.Stop_loop -> ());

      (* If we have no more to process in the stack, then we're
         done *)
      if Stack.length visited_stack = 0
      then raise W.Stop_loop
      else
        (* Here we're forced to start moving rightward *)
        let temp = Stack.pop visited_stack in
        Printf.sprintf "%s " temp.data |> print_string;
        iter_node := temp.right
    done
  with W.Stop_loop -> ()

let () = 
  let root = new_node "F" in

  ["B";"G";"A";"D";"I";"C";"E";"H"] |> List.iter (insert root);
  in_order_traversal root;
  print_newline ();

Answer 2

Asking for someone to write something without recursive calls is stupid, but I'll still do it because it's an interesting exercise. Going from recursive to iterative is always the same process.

type tree = Leaf | Node of int * tree * tree

let rec in_order = function
  | Leaf -> []
  | Node(i,l,r) -> in_order l @ (i :: in_order r);;

Alright, now we have our recursive function. The first step is to transform it to tail recursive. This is actually the hardest step since it requires a real logical and algorithmic change.

We are going to add a new parameter to the function that is going to contain the result of the computation :

 let rec ino res = function
  | Leaf -> ()
  | Node(i,l,r) -> 
    begin
      ino res r ;
      res := i :: !res ;
      ino res l
    end

At the end, the result is !res.

Now that we have this, removing the recursive call is very easy, we just have to think about what does the compiler does when he has a recursive call. Well, it just does a while loop, after putting the parameters of the function and the next work to do in a stack. Let's just do it.

open Stack
type work = Value of int | NextNode of tree ref

let ino t : int list =
  let res = ref [] in
  let stack = Stack.create () in
  push (NextNode (ref t)) stack;
  try
    while true do
      let current = pop stack in
      match current with 
      Value i -> res := i :: !res
    | NextNode n ->
      begin
        match !n with
        Leaf -> ()
          | Node(i,l,r) -> 
        begin
          push (NextNode (ref l)) stack;
          push (Value i) stack;
          push (NextNode (ref r)) stack
        end
      end
    done;
    assert false
  with
    | Empty -> !res

Here we just remember the next thing to do. We know that when we reach a node we have to treat its right child, then the value of the node, then its left child, so we just put all this in the stack (in reverse order of course), and we keep going to the next element of the stack. When the stack is empty, we have visited the whole tree, and we can return.

I hope that this post manages to convince some people of the power of recursion over iterative programming. 3 lines Vs 26 lines. QED.