Challenge 13: Danny's Revenge

When Dr. Danny Chen isn't cranking out a gazillion papers out per month, he is probably devising mindtwisters to torture his Algorithms¹ students (among many other things). One of his favorite problems is to take an ordinary data structure and require the students to augment it with a new method or algorithm in an efficient and optimal manner.

For this problem, you are to implement a simple binary search tree and augment it with a new FindLowestCommonAncestor method which returns the lowest or nearest common ancestor of two nodes in the BST. Note, that a node can be considered the ancestor of itself.

Consider the tree to the right:

• The LCA for 1 and 7 is 3
• The LCA for 4 and 14 is 8.
• The LCA for 7 and 6 is 6.

You are to augment a BST with an implementation of this LCA method that has a complexity better than O(n).

Input

The input will be a series of BSTs. The first line will specify the number of nodes in the tree. This will be followed by the nodes themselves. The next line will indicates the number of node pairs to compute the LCA on, followed by the pairs, one on each line. The input will be terminated by a -1 as the first line of the test case.

Example Input

9
8 3 10 1 6 14 4 7 13
3
1 7
4 14
7 6
-1

Output

For each test case, output the LCA. Separate outputs from different trees with a blank line.

Example Output

3
8
6

Submission

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

$ cd path/to/cse-30872-fa17-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

$ curl -F source=@challenge13/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa17/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.