Display(iter) a Sorted Binary Tree in Order

Learning
1

I created a simple sorted binary tree(see below) and I decided to display(iter) the contents of the tree in order of smallest to largest.

module MyBtree =
  struct

    type 'a btree = Empty | Btree of ('a * 'a btree * 'a btree)

    let empty = Empty

    let rec display toString bt =
      match bt with
      | Empty -> print_endline "Empty"
      | Btree (d, left, right) ->
        print_endline (toString d);
        display toString left;
        display toString right

    let rec add data bt =
      match bt with
      | Empty -> Btree (data, Empty, Empty)
      | Btree (d, left, right) ->
        if (data < d)
        then
          Btree (d, add data left, right)
        else if (data > d)
        then
          Btree (d, left, add data right)
        else 
          bt

    type 'a btreeList = Data of 'a | Node of 'a btree

    let buildLeftList bt =
      let rec buildLeftListAux bt acc =
        match bt with
        | Empty -> acc
        | Btree (d, left, right) ->
          buildLeftListAux left ((Data d)::(Node right)::acc) in
      buildLeftListAux bt []

    let buildList bL =
      let rec buildListAux bL acc =
        match bL with
        | [] -> List.rev acc
        | hd::tl ->
          (
            match hd with
            | Data d -> buildListAux tl (d::acc)
            | Node bt -> buildListAux ((buildLeftList bt) @ tl) acc
          ) in
      buildListAux bL []

    let iter func bt = List.iter func (buildList (buildLeftList bt))

  end

let b =
  List.fold_left
    (fun acc elem -> MyBtree.add elem acc)
    MyBtree.empty
    [10; 1; 9; 2; 8; 3; 7; 4; 6; 5;]

let () =
  b
  |> MyBtree.display string_of_int

let () = print_endline "\n\n"

let () = 
  b
  |> MyBtree.iter (fun x -> Printf.printf "%d\n" x)

Now the code works but is there a way to accomplish the same thing without building a list(or other data container) to sort/hold the data?

2

Your function display nearly works without all the meandering of buildList, the only issue is that you are displaying the node data before the data of the left subtree,

  | Btree (d, left, right) ->
        print_endline (toString d);
        display toString left;
        display toString right

which can be fixed with

  | Btree (middle, left, right) ->
        display toString left;
        print_endline (toString middle);
        display toString right
1 Like
3

You are correct!

My apologies, the description I posted was incomplete. What I really wanted was a next function that provided the next value(from smallest to largest) and a remainder of the values.

I found with a next type function you have to(I have to) build another data container to hold the data.

That being said, I should be able to modify the display function with a list accumulator and get my ordered values.

4

In this case, you might want to have a look at sequences defined in the Seq module defined in the standard library. They are a kind of lazy list with a next function. In particular, you could try to define a function:

let to_seq: 'a btree -> 'a Seq.t

In this kind of situation, there is often at least two way to store date: either explicitly in a data container or implicitly by storing data in closures or in the stack.

1 Like
5

I looked up the Seq docs and though trial and error I think figured out how it works… BTW I never did find the next function.

module MyBtree =
struct

  type 'a btree = Empty | Btree of ('a * 'a btree * 'a btree)

  let empty = Empty

  let rec display toString bt =
    match bt with
    | Empty -> print_endline "Empty"
    | Btree (d, left, right) ->
      display toString left;
      print_endline (toString d);
      display toString right

  let rec add data bt =
    match bt with
    | Empty -> Btree (data, Empty, Empty)
    | Btree (d, left, right) ->
      if (data < d)
      then
        Btree (d, add data left, right)
      else if (data > d)
      then
        Btree (d, left, add data right)
      else
        bt

  type 'a buildList = Data of 'a | BNode of 'a btree

  let buildLeft bt =
    let rec buildLeftAux bt acc =
      match bt with
      | Empty -> acc
      | Btree (d, left, right) ->
        buildLeftAux left ((Data d)::(BNode right)::acc) in
    buildLeftAux bt []

  let to_seq bt =
    let bL = buildLeft bt in
    let rec to_seq_aux bL =
      match bL with
      | [] -> Seq.empty
      | hd::tl ->
        (
          match hd with
          | Data d -> fun () -> Seq.Cons(d, to_seq_aux tl)
          | BNode bt -> to_seq_aux ((buildLeft bt) @ tl)
        ) in
    to_seq_aux bL

end

let b =
  List.fold_left
    (fun acc elem -> MyBtree.add elem acc)
    MyBtree.empty
    [10; 1; 9; 2; 8; 3; 7; 4; 6; 5;]

let () =
  b
  |> MyBtree.display string_of_int

let () = print_endline "\n\n"

let mySeq = MyBtree.to_seq b

let () = Seq.iter (fun x -> Printf.printf "%d " x) mySeq

Thank-you for the pointers.

6

You can also avoid buildLeft with


let rec append left right () = match left () with
| Seq.Nil -> right ()
| Seq.Cons(x, left) -> Seq.Cons(x, append left right)

let to_seq tree () = match tree with
| Empty -> Seq.Nil
| Btree(mid,left,right) ->
   append (to_seq left) (append (Seq.return mid) (to_seq right)) ()

Concerning the next function, you can see the sequence itself as a next function for the underlying data or computation.

7

You might be interested in looking at how the many combinators in oseq are implemented.

2 Likes
8

An alternative is to use a zipper.
https://en.wikibooks.org/wiki/Haskell/Zippers

9

Tried rewriting my code, knowing that my initial try way was meandering(thanks for pointing that out BTW), and here’s where I’m at currently:

module MyBtree =
  struct

    type 'a btree = Empty | Btree of ('a * 'a btree * 'a btree)

    let empty = Empty

    let rec display toString bt =
      match bt with
      | Empty -> print_endline "Empty"
      | Btree (d, left, right) ->
        display toString left;
        print_endline (toString d);
        display toString right

    let rec add data bt =
      match bt with
      | Empty -> Btree (data, Empty, Empty)
      | Btree (d, left, right) ->
        if (data < d)
        then
          Btree(d, add data left, right)
        else if (data > d)
        then
          Btree(d, left, add data right)
        else
          bt

    let to_list bt =
      let rec to_list_aux bt acc =
        match bt with
        | Empty -> acc
        | Btree (d, left, right) ->
          to_list_aux left (d :: (to_list_aux right acc)) in
      to_list_aux bt []

    let to_seq bt =
      let rec to_seq_aux bt acc =
        match bt with
        | Empty -> acc
        | Btree (d, left, right) ->
          to_seq_aux left (fun () -> Seq.Cons(d, (to_seq_aux right acc))) in
      to_seq_aux bt (fun () -> Seq.Nil)

  end

let b =
  List.fold_left
    (fun acc elem -> MyBtree.add elem acc)
    MyBtree.empty
    [10; 1; 9; 2; 8; 3; 7; 4; 6; 5;]

let () =
  b
  |> MyBtree.display string_of_int

let () = print_endline "\n\n"

let () =
  b
  |> MyBtree.to_list
  |> List.iter (fun x -> Printf.printf "(List)%d " x)

let () = print_endline "\n\n"

let () =
  b
  |> MyBtree.to_seq
  |> Seq.iter (fun x -> Printf.printf "(Seq)%d " x)

Not as elegant as the posted solutions but I have to work within my own skills for this to make sense.

10

Note that I thought that your initial code was meandering because your initial stated aim was an iter function; whereas your actual code was quite close of implementing a full zipper as suggested by @toolslive . Zipper or sequence code tend to be more complex to write than internal iterators because they require to give the control to the user.