# Difference between revisions of "99 questions/Solutions/64"

(Another solution) |
(categorize) |
||

Line 51: | Line 51: | ||

rightsHelper Empty = 0 |
rightsHelper Empty = 0 |
||

</haskell> |
</haskell> |
||

+ | |||

+ | [[Category:Programming exercise spoilers]] |

## Latest revision as of 03:41, 10 January 2017

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
```