Convert a binary search tree into a linked list in place.

bst_to_ll.ml

(**
 * This file contains 3 ways to solve the problem of:
 *
 *   converting a binary search tree into a sorted linked list in-place
 *
 * In place means that no extra memory should be used, no structures are copied
 *
 * 1. Using ref nodes
 * 2. Using records with mutable fields
 * 3. Using immutable Cons and Nil linked list
 *
 * The 3rd way is not in-place, but I thought it would be interesting to code it out anyway.
 *
 * Example tree we will use in all our examples:
 *
 *      8
 *    /   \
 *   4     10
 *  / \   / \
 * 1   6  9   12
 *
 * *)

(**
 * Implementation 1: ref nodes
 * The left child, right child are references.
 * It's an option type because nodes might not have either/both children.
 * The last reference is the next pointer in the linked list.
 * *)
type 'a refnode =
    RefNode of
      'a                    (* value *)
    * 'a refnode option ref (* left  *)
    * 'a refnode option ref (* right *)
    * 'a refnode option ref (* next  *)

(* Set n's next node to next. *)
let set_next n next = match n with
  RefNode(v, _, _, n') -> n' := next

(**
 * Convert bst (with left and right refs) into a linked list, by setting the next ref.
 *
 * The algorithm is recursive and has 3 steps:
 *   - convert the left subtree into a linked list
 *   - convert the right subtree into a linked list
 *   - merge the left linked list with the current node and the right linked list
 * Each conversion will return the head and last node of the linked list so that
 * merging can happen without traversing the entire list.
 * *)
let ref_convert bst: 'a refnode =
  let rec helper n : ('a refnode * 'a refnode) =
    match n with
    | RefNode(v, l, r, next) ->
      let lh, lt =
        begin
          match !l with
          | None -> RefNode(v, l, r, next), RefNode(v, l, r, next)
          | Some left -> let lh, lt = helper left in set_next lt (Some n); lh, lt
        end
      in
      let rh, rt =
        begin
          match !r with
          | None -> RefNode(v, l, r, next), RefNode(v, l, r, next)
          | Some right -> let rh, rt = helper right in set_next n (Some rh); rh, rt
        end
      in
      lh, rt
  in
  fst (helper bst)

(* Prints the resulting linked list *)
let rec pr_ref_list (n : int refnode) = match n with
  | RefNode (v, _, _, next) ->
    begin
      match !next with
      | None -> string_of_int v
      | Some n -> string_of_int v ^ ", " ^ (pr_ref_list n)
    end

(* Example for ref node *)
let n1 = RefNode(1, ref None, ref None, ref None)
let n6 = RefNode(6, ref None, ref None, ref None)
let n4 = RefNode(4, ref (Some n1), ref (Some n6), ref None)
let n9 = RefNode(9, ref None, ref None, ref None)
let n12 = RefNode(12, ref None, ref None, ref None)
let n10 = RefNode(10, ref (Some n9), ref (Some n12), ref None)
let n8 = RefNode(8, ref (Some n4), ref (Some n10), ref None)

let _ = n8 |> ref_convert |> pr_ref_list |> print_endline

(**
 * Implementation 2: record with mutable fields
 * The left child, right child, and next pointer in linked list are
 * ref types in the record.
 * *)
type 'a recnode = {
  value: 'a;
  mutable left: 'a recnode option;
  mutable right: 'a recnode option;
  mutable next: 'a recnode option;
}

(**
 * The algorithm is the same as the ref node implementation.
 * *)
let record_convert (bst : 'a recnode) : 'a recnode =
  let rec helper n : ('a recnode * 'a recnode) =
    let lh, lt =
      begin
        match n.left with
        | None -> n, n
        | Some left -> let lh, lt = helper left in lt.next <- Some n; lh, lt
      end
    in
    let rh, rt =
      begin
        match n.right with
        | None -> n, n
        | Some right -> let rh, rt = helper right in n.next <- Some rh; rh, rt
      end
    in
    lh, rt
  in
  fst (helper bst)

(* Prints the resulting linked list *)
let rec pr_record recnode = match recnode.next with
  | None -> string_of_int recnode.value
  | Some next -> string_of_int recnode.value ^ ", " ^ (pr_record next)

(* Example for record node *)
let nn1 = { value = 1; left = None; right = None; next = None }
let nn6 = { value = 6; left = None; right = None; next = None }
let nn9 = { value = 9; left = None; right = None; next = None }
let nn12 = { value = 12; left = None; right = None; next = None }
let nn4 = { value = 4; left = Some nn1; right = Some nn6; next = None }
let nn10 = { value = 10; left = Some nn9; right = Some nn12; next = None }
let nn8 = { value = 8; left = Some nn4; right = Some nn10; next = None }

let _ = nn8 |> record_convert |> pr_record |> print_endline

(**
 * Implementation 3: immutable structure
 * A tree is an ADT, either a Leaf, or a Node that has left and right subtrees.
 * A llist is a linked list, either a Cons of a head and tail (llist), or Nil (end of list).
 * *)
type 'a tree = Leaf of 'a | Node of ('a tree) * 'a * ('a tree)
type 'a llist = Nil | Cons of 'a * 'a llist

(* Appends l' to l *)
let rec append l l' = match l, l' with
  | Nil, Nil -> Nil
  | Nil, l' -> l'
  | l, Nil -> l
  | Cons (a, al), l' -> Cons (a, append al l')

(**
 * Immutable makes things slightly different because we have to always copy the list,
 * so we don't have to return the head and last node of the list in each call
 * *)
let convert bst : 'a llist =
  let rec helper node : 'a llist =
    match node with
    | Leaf a -> Cons(a, Nil)
    | Node (l, n, r) ->
      let l_hd = helper l in
      let r_hd = helper r in
        append (append l_hd (Cons (n, Nil))) r_hd
  in
  helper bst

(* Prints the resulting linked list *)
let rec pr_lst ls = match ls with
  | Nil -> ""
  | Cons (hd, tl) ->
    begin
      match tl with
      | Cons _ -> (string_of_int hd) ^ ", " ^ (pr_lst tl)
      | Nil -> string_of_int hd
    end

(* Example for immutable structure *)
let bst = Node (Node(Leaf(1), 4, Leaf(6)), 8, Node(Leaf(9), 10, Leaf(12)))

let _ = bst |> convert |> pr_lst |> print_endline