Copyright | Copyright (C) 2021 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

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

# Documentation

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.

### Examples

`>>>`

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

### Notes

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.