# 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
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