Loading...
Loading...
Loading...
Meera draws her family tree for a school project as a binary tree and wants to read it in columns.
The root is in column 0. A left child is one column to the left of its parent, and a right child is one column to the right. The root is on row 0, and each child is one row below its parent.
Print the columns from left to right, one line per column. In each line, print the values from the top row down. If two values share both the row and the column, print the smaller value first. For an empty tree, print EMPTY.
N for no node. Children are listed only for real nodes, and N tokens at the end of the line may be left out. An empty tree is the single token N.EMPTY.Example
Input
3 9 20 N N 15 7 N N N N
Output
9 3 15 20 7
Node 15 is the left child of 20, so it lands in column 0 under the root 3.
Try the problem first. Open one hint at a time.
Give every node two numbers: its column and its row. Both come straight from its parent.
Values must come out grouped by column, then by row, then by value. Collect all of that before printing anything.
A walk level by level visits nodes row by row, so top-to-bottom comes for free. Ties inside a row still need sorting by value.
Use a breadth-first walk with a queue to record (column, row, value) for each node, then sort the records. A TreeMap from column to list also works.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor