# Problem 63

We define a left-justified, complete binary tree with height H as a tree where:

• levels 1,...,H-1 contain the maximum number of nodes,
• and in level H all the nodes are "left-justified", that is, as far to the left is possible.

Construct such a complete tree of unknown height, with `n` nodes containing `v` as label.

## Example for `v='x'` and `n=4`:

``````completeTree 'x' 4 ==
Node 'x' (Node 'x' (Node 'x' Empty Empty) Empty) (Node 'x' Empty Empty)
``````

## Unit Test

``````import Html
import List

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

completeTree : a -> Int -> Tree a
completeTree v 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)
[ completeTree 'x' 0 == Empty
, completeTree 'x' 1 == Node 'x' Empty Empty
, completeTree 'x' 3 == (Node 'x' (Node 'x' Empty Empty) (Node 'x' Empty Empty))
, completeTree 'x' 5 == (Node 'x'
(Node 'x' (Node 'x' Empty Empty) (Node 'x' Empty Empty))
(Node 'x' Empty Empty))
]
``````

## Hints

Heaps commonly use complete binary trees as data structures or addressing schemes. We can assign an address to each node in a complete binary tree by enumerating the nodes in level-order starting at the root with number 1. For every node `X` with address `A` the following holds: The address of `X`'s left and right successors are `2*A` and `2*A+1`, respectively, if they exist. This fact can be used to elegantly construct a complete binary tree structure.

Solutions