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')

Back to problem