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-fa22-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ 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 GitHub

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

$ .scripts/check.py
Checking challenge13 program.cpp ...
  Result Success
    Time 0.57
   Score 6.00 / 6.00

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