# Problem 65

``````{-| 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 =
let
ld = leftDepth 0 tree
x = 2 ^ ld - 1
sep = x
sep_ = sep // 2
in
case tree of
Empty ->
Empty

Node n left right ->
Node ( n, (x, 1) )
(layout_ (x - sep_ - 1) 2 sep_ left)
(layout_ (x + sep_ + 1) 2 sep_ right)

layout_ : Int -> Int -> Int -> Tree comparable -> Tree ( comparable, (Int, Int) )
layout_ x y sep tree =
let
sep_ = sep // 2
in
case tree of
Empty ->
Empty

Node n left right ->
Node ( n, (x, y) )
(layout_ (x - sep_ - 1) (y + 1) sep_ left)
(layout_ (x + sep_ + 1) (y + 1) sep_ right)

depth : Int -> Tree a -> Int
depth d tree =
case tree of
Empty ->
d

Node v left right ->
max (depth (d + 1) left) (depth (d + 1) right)

-- apply a function to each node, passing the depth as a parameter
leftDepth : Int -> Tree a -> Int
leftDepth d tree =
case tree of
Empty ->
d

Node v left right ->
max (leftDepth (d + 1) left) (leftDepth (d - 1) right)
``````

Back to problem