Loading...
Loading...
Loading...
Meera's library app keeps book IDs sorted. Inserting them one by one in that order would make a long chain and slow searches. She wants a balanced binary search tree instead.
Build it like this: the middle value of the list is the root, the values to its left form the left subtree, and the values to its right form the right subtree, built the same way. When a part has an even length, take the left of the two middle values. For a part from index lo to hi, that is index (lo + hi) / 2.
Print the tree in level order.
N for every missing child of a real node, so each real node is followed later by exactly two entries for its children.Example 1
Input
4 1 2 3 4
Output
2 1 3 N N N 4 N N
The left middle of 1 2 3 4 is 2. The left part is just 1. In 3 4 the left middle is 3, and 4 becomes its right child.
Example 2
Input
7 -30 -20 -10 0 10 20 30
Output
0 -20 20 -30 -10 10 30 N N N N N N N N
An odd length has one middle at every step, so the tree is perfectly full.
Try the problem first. Open one hint at a time.
The root must be the middle value. Everything smaller goes to its left, everything larger to its right.
Each half is the same problem on a smaller part of the list. Pass the two end indexes, not new lists.
A part with lo > hi is empty and gives no node.
For the output, walk the finished tree level by level with a queue, printing N for each missing child.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor