# Problem 64

To draw a tree a layout algorithm determines the position of each node in a rectangular grid. Several layout methods are conceivable, one of them is illustrated below:

In this layout strategy, the following two rules determine the position:

• `x(v)` is equal to the position of the node `v` in the inorder sequence
• `y(v)` is equal to the depth of the node `v` in the tree.

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

``````tree64 =
Node 'n'
(Node 'k'
(Node 'c'
(Node 'a' Empty Empty)
(Node 'h'
(Node 'g'
(Node 'e' Empty Empty)
Empty)
Empty))
(Node 'm' Empty Empty))
(Node 'u'
(Node 'p'
Empty
(Node 's'
(Node 'q' Empty Empty)
Empty))
Empty)

layout tree64 ==
Node ('n',(8,1)) (Node ('k',(6,2)) (Node ('c',(2,3)) ...
``````

## Unit Test

``````
import Html
import List

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

tree64 =
Node 'n'
(Node 'k'
(Node 'c'
(Node 'a' Empty Empty)
(Node 'h'
(Node 'g'
(Node 'e' Empty Empty)
Empty)
Empty))
(Node 'm' Empty Empty))
(Node 'u'
(Node 'p'
Empty
(Node 's'
(Node 'q' Empty Empty)
Empty))
Empty)

layout : Tree a -> Tree (a, (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 tree64
in
List.all ((==) True)
[ t == layout64
]

layout64 =
Node ('n', (8, 1))
(Node ('k', (6, 2))
(Node ('c', (2, 3))
(Node ('a', (1, 4)) Empty Empty)
(Node ('h', (5, 4))
(Node ('g', (4, 5))
(Node ('e', (3, 6)) Empty Empty)
Empty)
Empty))
(Node ('m', (7, 3)) Empty Empty))
(Node ('u', (12, 2))
(Node ('p', (9, 3))
Empty
(Node ('s', (11, 4))
(Node ('q', (10, 5)) Empty Empty)
Empty))
Empty)
``````

## Hints

1. You can simplify the problem by breaking down into two or more steps, traversing once to set the X, once to set the Y. You can model `List.indexedMap` to create traversal functions wtih depth or in-order.
2. The problem can be solved in a single traversal. You'll probably need nested `let` clauses to get the in-order values from subtree traversals.

Solutions