ninetynine-1.1.0: Ninety-Nine Haskell Problems
CopyrightCopyright (C) 2021 Yoo Chung
Safe HaskellSafe-Inferred



Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P64.



layoutInorder :: Tree a -> Tree (a, (Int, Int)) Source #

Let's say we want to draw a binary tree. In preparation, 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 in-order 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)\) is the top left corner of the rectangle bounding the drawn tree.


>>> layoutInorder tree64
Branch ('n',(8,1)) (Branch ('k',(6,2)) (Branch ('c',(2,3)) ...



In fact, the image was rendered to SVG using the return value of layoutInorder with writeSVG. The images for Problems.P65 and Problems.P66 were also rendered similarly.

tree64 :: Tree Char Source #

Tree used as the example for Problems.P64.