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 =
    treeMap addXY tree
      |> treeMapDepth setY 1
      |> treeMapInOrder setX 1


addXY : a -> (a, (Int, Int))
addXY v =
    (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