CODEWITHSUNDEEP
ocaml
james king
james king

Reputation: 90

Creating a perfectly balanced binary tree in ocaml

I have been writing some code to try make a perfectly balanced tree from an array though i run into issues when I tree and make the list bigger than 3 elements i get the error "Stack overflow during evaluation (looping recursion?)". I was if this is was because my quite inefficient implementation or of some other mistake I have made? Thanks for any help it will be greatly appreciate, code below.

ps - I also realise I should have used fold_left for the helper functions but I did not them understand it till after doing this

 type 'a binary_tree =
      | Empty
      | Node of 'a * 'a binary_tree * 'a binary_tree;;


 let length lst = 
     let rec aux acc = function
          | [] -> acc
          | x::xs -> aux (acc+1) xs
     in
     aux 0 lst;;

 let mid lst = 
     let rec aux count = function
         | [] -> None
         | x::xs -> if (count=0) then Some x else aux (count-1) xs
     in
     aux ((length lst)/2) lst;;

  let left lst = 
      let rec aux count acc = function
           | [] -> []
           | x::xs -> if (count=0) then acc else aux (count-1) (acc@[x]) xs
       in
       aux ((length lst)/2) [] lst;;


  let right lst = 
      let rec aux count = function
          | [] -> []
          | x::y::xs -> if (count=0) then xs else aux (count-1) (y::xs)
      in
      aux (((length lst)/2)-1) lst;;

  let rec createTree lst = match lst with
      | [x] -> Node((Some x),Empty,Empty)
      | xs -> Node((mid xs), (createTree(left xs)), (createTree(right xs)));;

Upvotes: 1

Views: 1071

Answers (2)

ghilesZ
ghilesZ

Reputation: 1586

You can use List.length directly instead of defining it yourself ;)

Also, if you dont particularily need to preserve the order of your elements, you can compute your mid, left and right values by taking the first element of a list, and splitting the rest as in the following :

let split l = 
  let rec loop left right flag rest =
    match rest with
    | [] -> left,right
    | h::t -> 
       if flag then loop (h::left) right (not flag) t
       else loop left (h::right) (not flag) t
  in loop [] [] true l

By switching flag to not flag at every step, you send one in every two element into the left list, and the other into the right one. Your createTree function thus becomes :

let rec createTree lst = 
  match lst with
  | [] -> Empty
  | h::t -> 
    let left,right = split t in  
    Node(h, (createTree left), (createTree right))

Hope it will help :)

Upvotes: 1

octachron
octachron

Reputation: 18902

Notwithstanding the implementation efficiency, the recursive loop stems from the missing empty case []: since left [] = [] and right [] = [], createTree [] is extended to Node(mid [], createTree [], createTree []) which leads to the stack overflow.

On the efficiency side, note that your worse function is left which is quadratic rather than linear in its input size due to the list concatenation acc @ [x] which is computed for each elements. For this case, performance will be much better by reversing the list at the end of left.

Another point, it could make sense to group together left, mid, right in a partition function to avoid some repetitions.

Upvotes: 3

Related Questions