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

main =
Html.text
(if (test) then
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