CODEWITHSUNDEEP
ocamlbinary-tree
mvxxx
mvxxx

Reputation: 115

Ocaml, levels function for binary tree

I want to implement levels function for binary tree which transform binary tree into list list int and each of list int need to contain all values at current level: For example:

              9
         6          10
     5     7              11
 42   
 42
 42

[[9];[6;10];[5;7;11];[42];[42];[42]]

I need use this type and fold_bin_tree

type 'a bin_tree =
   Node of 'a bin_tree * 'a * 'a bin_tree | Null;;


let rec fold_bin_tree f a t =
  match t with
  Null ->a |
  Node (l,x,r) ->f x (fold_bin_tree f a l) (fold_bin_tree f a r);;

I have implemented merge function as a helper and that is my code:

let merge l1 l2 = (*[[a b c] [d e]] merge [[1] [2 3] [4]] = 
[[a b c 1] [d e 2 3] [4]]*)
let rec scan l1 l2 acc =
  match l1,l2 with
  | [],[] -> acc
  | h1::t1,[] -> scan t1 l2 (h1::acc)
  | [], h2::t2 -> scan l1 t2 (h2::acc)
  | h1::t1,h2::t2 -> scan t1 t2 ((h1@h2)::acc)
  in scan l1 l2 [];;

let levels t =
  fold_bin_tree
  (fun x levels_l levels_r -> let lev = merge levels_l levels_r in
    [x]::lev
  ) [] t;;

I have tested merge and it seems to work well, but my levels does not work correctly because 

levels example

returns [[9];[5;7];[42];[42];[42;11];[6;10]]

where example is that tree which I have shown at the begin of my post

  let example = Node(  Node(Node(Node(Node(Node(Null,42,Null),42,Null),42,Null),5,Null), 6 ,Node( Null, 7 ,Null )) ,9, (Node(Null, 10 ,Node(Null,11,Null))));;

Upvotes: 0

Views: 425

Answers (1)

octachron
octachron

Reputation: 18902

Hint: Why do your function merge returns

 merge [[1];[2]] [];;

[[2]; [1]]

?

Upvotes: 2

Related Questions