Problem 55
Solution 1
Use List.foldl, adds one node at a time.
balancedTree : Int -> Tree Char
balancedTree n =
List.foldl (addBalancedNode) Empty <| List.repeat n 'x'
addBalancedNode : a -> Tree a -> Tree a
addBalancedNode v tree =
case tree of
Empty ->
Node v Empty Empty
Node v' left right ->
if count left > count right then
Node v' left (addBalancedNode v right)
else
Node v' (addBalancedNode v left) right
-- count number of Nodes in a Tree
count : Tree a -> Int
count tree =
case tree of
Empty -> 0
Node n left right ->
1 + (count left) + (count right)
Solution 2
A more efficient solution adds many nodes at once.
import Html
import List
import String
type Tree a
= Empty
| Node a (Tree a) (Tree a)
balancedTree : Int -> Tree Char
balancedTree n =
if n < 1 then
Empty
else
case n of
1 ->
Node 'x' Empty Empty
n ->
let
n' = (n-1) // 2
in
if n % 2 == 1 then
Node 'x' (balancedTree n') (balancedTree n')
else
Node 'x' (balancedTree (n' + 1)) (balancedTree n')