Problem 65

The illustration below depicts an alternative layout method.

Find out the rules and write the corresponding function. Hint: On a given level, the horizontal distance between neighboring nodes is constant. Write a function to annotate each node of the tree with its position.

To solve this problem you will need to traverse the tree. Problems 68a, 68b, and 68c examine tree traversal.

Example

tree65 = 
    Node 'n'
        (Node 'k'
            (Node 'c'
                (Node 'a' Empty Empty)
                (Node 'e'
                    (Node 'd' Empty Empty)
                    (Node 'g' Empty Empty)))
            (Node 'm' Empty Empty))
        (Node 'u'
            (Node 'p' 
                Empty 
                (Node 'q' Empty Empty)) 
            Empty)


layout65 tree65 ==
    Node ('n',(15,1)) 
        (Node ('k',(7,2)) 
            (Node ('c',(3,3)) ...

Unit Test

import Html
import List


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


tree65 = 
    Node 'n'
        (Node 'k'
            (Node 'c'
                (Node 'a' Empty Empty)
                (Node 'e'
                    (Node 'd' Empty Empty)
                    (Node 'g' Empty Empty)))
            (Node 'm' Empty Empty))
        (Node 'u'
            (Node 'p' 
                Empty 
                (Node 'q' Empty Empty)) 
            Empty)



{-| Given a Tree return a tree that adds x, y coordinates for each node
    to layout a graphic representation of the tree
-}
layout : Tree comparable -> Tree ( comparable, (Int, Int) )
layout tree =
    -- your implementation goes here
    Empty


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


test : Bool
test =
    let 
        t = layout tree65 
    in 
        List.all ((==) True)
          [ t == layout65
          ]

layout65 = 
    Node ('n', (15, 1))
        (Node ('k', (7, 2))
            (Node ('c', (3, 3))
                (Node ('a', (1, 4)) Empty Empty)
                (Node ('e', (5, 4))
                    (Node ('d', (4, 5)) Empty Empty)
                    (Node ('g', (6, 5)) Empty Empty)))
            (Node ('m', (11, 3)) Empty Empty))
        (Node ('u', (23, 2))
            (Node ('p', (19, 3)) 
                Empty 
                (Node ('q', (21, 4)) Empty Empty)) 
            Empty)

Hints

1. Find out the rules and write the corresponding function. Hint: At a given depth, the horizontal distance between neighboring nodes is constant.
2. Need another hint? The horizontal distance is a function of the depth from the tree from that node and the depth of the left subtree.

Solutions

Solutions