Problem 64 Solutions

Solution 1

Set the x and y coordinates in a single pass using in-order traversal.

``````layout : Tree a -> Tree (a, (Int, Int))
layout tree =
layoutAux 1 1 tree
|> Tuple.first

layoutAux : Int -> Int -> Tree a -> (Tree (a,(Int,Int)), Int)
layoutAux x y tree =
case tree of
Empty ->
(Empty, x)

Node n l r ->
let
(lTree, xl) = layoutAux x (y+1) l
(rTree, xr) = layoutAux (xl+1) (y+1) r
in
(Node (n, (xl,y)) lTree rTree, xr)
``````

Solution 2

This solution breaks down the process into three steps,

• Inserting a coordinate to each node
``````treeMap addXY tree
``````
• Setting the y value to the depth
``````treeMapDepth setY 1
``````
• Setting the x value to the in-order index
``````treeMapInOrder setX 1
``````

This is not an efficient solution, as the tree must be traversed multiple times. However the traversal functions `treeMapDepth` and `treeMapInOrder` modeled on `List.indexedMap` will be useful functions for other problems.

``````layout : Tree a -> Tree (a, (Int, Int))
layout tree =
|> treeMapDepth setY 1
|> treeMapInOrder setX 1

addXY : a -> (a, (Int, Int))
(v, (0, 0))

setY : Int -> (a, (Int, Int)) -> (a, (Int, Int))
setY n (v, (x, y)) =
(v, (x, n))

setX : Int -> (a, (Int, Int)) -> (a, (Int, Int))
setX n (v, (x, y)) =
(v, (n, y))

treeMap : (a -> b) -> Tree a -> Tree b
treeMap f tree =
case tree of
Empty ->
Empty

Node v left right ->
Node (f v) (treeMap f left) (treeMap f right)

-- apply a function to each node, passing the depth as a parameter
treeMapDepth : (Int -> a -> b) -> Int -> Tree a -> Tree b
treeMapDepth f d tree =
case tree of
Empty ->
Empty

Node v left right ->
Node (f d v)
(treeMapDepth f (d + 1) left)
(treeMapDepth f (d + 1) right)

-- apply a function to each node, passing the in-order index as a parameter
treeMapInOrder : (Int -> a -> b) -> Int -> Tree a -> Tree b
treeMapInOrder f n tree =
case tree of
Empty ->
Empty

Node v left right ->
let
nn = (n + (treeCount left))
in
Node  (f nn v)
(treeMapInOrder f n left)
(treeMapInOrder f (nn + 1) right)

-- count number of Nodes in a Tree
treeCount : Tree a -> Int
treeCount tree =
case tree of
Empty -> 0

Node n left right ->
1 + (treeCount left) + (treeCount right)
``````

Back to problem