Challenge 13: Taeho's Tree

When Taeho isn't busy working on crazy crypto research in his DSP lab, he is most likely thinking of devious ways of destroying the students in algorithms. For example, he recently came up with the following challenge:

Given a sequence of integers in ascending order, create a minimal binary search tree (that is, the tree has the minimum necessary height) and display all the nodes in the tree level by level.

Since most of his students have already taken Data Structures, they immediately suggested an approach that involves reading the sequence of integers and inserting into a binary search tree. Once the BST is constructed, it could be printed out by using a simple traversal.

Taeho smirked at this suggestion and politely said that while this works, it runs in O(nlogn) time... and that there is a better approach that utilizes divide and conquer to run in O(N) time.

You are to implement this more efficient version.

Input

You will be given a series of lines, where each line contain a sequence of integers in ascending order:

Example Input

0 1 2 3 4 5 6

Output

For each sequence of integers, you are to output the binary search tree constructed from the sequence of integers by displaying all the nodes in the BST level by level:

Example Output

3
1 5
0 2 4 6

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa18-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge13               # Create and checkout challenge13 branch

$ $EDITOR challenge13/program.cpp           # Edit your code

$ git add challenge13/program.cpp           # Stage your changes
$ git commit -m "challenge13: done"         # Commit your changes

$ git push -u origin challenge13            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge13 assignment ...
Submitting challenge13 code ...
  Result Success
   Score 6.00
    Time 0.92

$ curl -F source=@challenge13/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa18/challenge13
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 07 TA List to determine your corresponding TA for the merge request.