Problem 55

In a balanced binary tree the difference between the number of nodes in the left and right subtrees of every node is less than one.

Write a function to construct a balanced binary tree for a given number of nodes. Put the letter 'x' as data value for all nodes of the tree.

Example

balancedTree 3 == 
    (Node 'x' 
        (Node 'x' (Empty) (Empty)) 
        (Node 'x' (Empty) (Empty)))

Unit Test

import Html
import List
import String


type Tree a
    = Empty
    | Node a (Tree a) (Tree a)


balancedTree : Int -> Tree Char
balancedTree n =
    -- your implementation here
    Empty


main =
    Html.text
        (if (test) then
            "Your implementation passed all tests."
         else
            "Your implementation failed at least one test."
        )


test : Bool
test =
    List.all ((==) True)
        [ count Empty == 0
        , count (Node 'x' (Empty) (Empty)) == 1
        , count (Node 'x' (Node 'x' (Empty) (Empty)) (Node 'x' (Empty) (Empty))) == 3
        , count (Node 'x'
                    (Node 'x' (Node 'x' (Empty) (Empty)) (Node 'x' (Empty) (Empty)))
                    (Node 'x' (Node 'x' (Empty) (Empty)) (Node 'x' (Empty) (Empty)))) == 7
        , balancedTree 0 == Empty
        , balancedTree -1 == Empty
        , balancedTree 1 == (Node 'x' (Empty) (Empty))
        , balancedTree 3 == (Node 'x' (Node 'x' (Empty) (Empty)) (Node 'x' (Empty) (Empty)))
        , balancedTree 7 == (Node 'x'
                                (Node 'x' (Node 'x' (Empty) (Empty)) (Node 'x' (Empty) (Empty)))
                                (Node 'x' (Node 'x' (Empty) (Empty)) (Node 'x' (Empty) (Empty))))
        , testBalance (balancedTree 3) 3 == True
        , testBalance (balancedTree 4) 4 == True
        , testBalance (balancedTree 5) 5 == True
        , testBalance (balancedTree 7) 7 == True
        , testBalance (balancedTree 21) 21 == True
        , testBalance (balancedTree 31) 31 == True
        , testBalance (balancedTree 32) 32 == True
        , testBalance (balancedTree 33) 33 == True
        , testBalance (balancedTree 59) 59 == True
        , testBalance (balancedTree 64) 64 == True
        , testBalance (balancedTree 73) 73 == True
        , testBalance (balancedTree 5000) 5000 == True
        ]


testBalance : Tree a -> Int -> Bool
testBalance tree n =
    case tree of
        Empty ->
            n == 0

        Node node left right ->
            List.all ((==) True)
              [ (abs (count left) - count (right)) < 2
              , count tree == n
              ]


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

Solutions

Solutions