Description

When Dr. Danny Chen isn't cranking out a gazillion papers out per month, he is probably devising mindtwisters to torture his Algorithms [1] 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 (BST) and augment it with a new FindLowestCommonAncestor method which returns the lowest or nearest common ancestor of two nodes in the BST. Consider the tree to the right: The LCA for 1 and 7 is 3, while the LCA for 4 and 14 is 8. You are to augment a BST with a O(logn) implementation of this LCA method.

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.

Sample input:

7
20 8 22 4 12 10 14
2
4 14
12 22
-1

Output

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

8
20

Approach

Using the properties of a BST, you can traverse from the root to the LCA by following the rules:

1. If the current node is less than both nodes, traverse right.
2. If the current node is greater than both nodes, traverse left.
3. LCA is found and return.

Input/Output

• Final Input: problem011.input
• Final Output: problem011.output

Source Code

• Peter Bui's source code: pbui.c
• Dominic Golab's source code: dgolab.cpp
• Raymond LeGrand's source code: rlegrand.cc