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

main =
        (if (test) then
            "Your implementation passed all tests."
            "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))


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.



results matching ""

    No results matching ""