# 99 questions/Solutions/65

< 99 questions | Solutions

Jump to navigation
Jump to search
An alternative layout method is depicted in the illustration below:

Find out the rules and write the corresponding function. Hint: On a given level, the horizontal distance between neighboring nodes is constant.

Use the same conventions as in problem P64 and test your function in an appropriate way.

```
layout :: Tree a -> Tree (a, Pos)
layout t = layoutAux x1 1 sep1 t
where d = depth t
ld = leftdepth t
x1 = 2^(d-1) - 2^(d-ld) + 1
sep1 = 2^(d-2)
layoutAux x y sep Empty = Empty
layoutAux x y sep (Branch a l r) =
Branch (a, (x,y))
(layoutAux (x-sep) (y+1) (sep `div` 2) l)
(layoutAux (x+sep) (y+1) (sep `div` 2) r)
depth :: Tree a -> Int
depth Empty = 0
depth (Branch a l r) = max (depth l) (depth r) + 1
leftdepth :: Tree a -> Int
leftdepth Empty = 0
leftdepth (Branch a l r) = leftdepth l + 1
```

The auxiliary function is passed the x- and y-coordinates for the root of the subtree, the horizontal separation between the root and its child nodes, and the subtree itself. It returns the subtree annotated with positions.