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