Problems.P64

Description

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

Synopsis

# 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

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


### Notes

Expand

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.

Tree used as the example for Problems.P64.