Binary Tree Drawing
Time limit2sMemory limit128 MB
Given a binary tree reconstructed from preorder and inorder traversals, compute the minimum area of a grid drawing where each right child extends the row and each down child extends the column.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Tree, Recursion
- Solved
- No attempts yet
Problem
You want to draw a binary tree on a two-dimensional grid. Each vertex is placed on a grid point, and the root of the whole drawing is placed at the top-left corner of the used grid.
A drawing must satisfy the following conditions.
- A child of a vertex is placed either to the right of its parent on the same row, or below its parent in the same column.
- If a vertex has two children, one child is placed in the right direction and the other in the downward direction. If it has one child, either direction may be chosen.
- For any vertex with two children, the two axis-aligned rectangles enclosing the subtrees rooted at those children must not overlap.
The area of a drawing is the product of the width and height of the grid needed to contain the whole drawing. Given the binary tree, compute the minimum possible area among all drawings that satisfy these conditions.
Input
The first line contains the number of vertices n. (1 <= n <= 100)
The second line contains n integers separated by spaces. Assume that the preorder traversal of the binary tree is 1, 2, ..., n; the given sequence is the inorder traversal of that tree. The input is always a valid tree satisfying this condition.
Output
Print the minimum possible area of a drawing that satisfies the conditions.