99 questions/Solutions/64

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