# 99 questions/Solutions/64

### From HaskellWiki

Given a binary tree as the usual Prolog term t(X,L,R) (or nil). As a preparation for drawing the tree, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable, one of them is shown in the illustration below:

In this layout strategy, the position of a node v is obtained by the following two rules:

- 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 a position, where (1,1) in the top left corner or the rectangle bounding the drawn tree.

type Pos = (Int, Int) layout :: Tree a -> Tree (a, Pos) layout t = fst (layoutAux 1 1 t) where layoutAux x y Empty = (Empty, x) layoutAux x y (Branch a l r) = (Branch (a, (x',y)) l' r', x'') where (l', x') = layoutAux x (y+1) l (r', x'') = layoutAux (x'+1) (y+1) r

The auxiliary function is passed the x-coordinate for the left-most node of the subtree, the y-coordinate for the root of the subtree, and the subtree itself.
It returns the subtree annotated with positions, plus the count of `Branch` nodes in the subtree.

The following is another solution. The root is located at (0, 0).

tree64 t = helper 0 0 t where helper x y Empty = Empty helper x y (Branch _ t0 t1) = let l = rights t0 r = lefts t1 in Branch (x,y) (helper (x - l) (succ y) t0) (helper (x + r) (succ y) t1) -- counting right steps caused by helper rights (Branch _ t0 t1) = rightsHelper t1 + 1 rights Empty = 0 -- counting left steps caused by helper lefts (Branch _ t0 t1) = leftsHelper t0 + 1 lefts Empty = 0 leftsHelper (Branch _ t0 t1) = rightsHelper t1 + leftsHelper t0 + 1 leftsHelper Empty = 0 rightsHelper (Branch _ t0 t1) = leftsHelper t0 + rightsHelper t1 + 1 rightsHelper Empty = 0