$O(n\log n)$- algorithm for finding tree root

All numbers from $1$ to $n = 2^k-1$ are written in unknown way in a full binary tree of height $k$. We say that a number $t$ lies between $i$ and $j$ if after removing $t$ from the tree we obtain that $i$ and $j$ are in different connectivity components. Propose an algorithm for determining a number in the root of tree asking $O(n\log n)$ questions of the type "Is $t$ lies between $i$ and $j$"? The answer may be "yes" or "no".

I will be gratefull for hints and ideas.

Routine 1
Firstly, observe that only the root node disconnects the tree into exactly two equal connected components of size $2^{k-2}-1$. All other nodes disconnect the tree into three or zero connected components. We have the following $\mathcal{O}(n)$ approach to check if a given node is the root.

• Let the node to check be $x$.

• Pick another node $y \not= x$

• Iterate through all other nodes $z \not\in \{x,y\}$ and ask if $x$ disconnects $y$ from $z$.

• If there are $2^{k-2}-1$ nodes in the connected component of $y$, then $x$ is a root, else it isn't.

Routine 2 Now, let's present an $\mathcal{O}(n)$ algorithm to identify leaves. Observe that a random node has $\ge 0.5$ probability of being a leaf node. Hence our algorithm is -

• Pick a random node in the tree, say $x$.

• Pick another random node $y$.

• If $x$ does not disconnect $y$ from $z$, for all valid $z$, then $x$ is a leaf node in the tree.

• Repeat steps 1, 2 and 3 till you obtain a leaf.

The expected number of queries used by this algorithm is $\mathcal{O}(n)$.

Routine 3 Now let's make the next observation. There are $2^{k-1}$ nodes in the last level of this complete binary tree. Colour these leaf nodes with two colours, red and blue. A leaf is coloured red if it belongs in the left sub tree of the root and blue otherwise. Using Routine 2, we will try to find a pair of leaf nodes one of which is red and the other is blue in $O(n)$ queries. Here is how -

• Find any leaf node using the algorithm in Routine 2. Call this leaf node $u$.

• Find a different leaf node, call this $v$.

• $u$ and $v$ are of different colour if and only if exactly $2k-1$ nodes can disconnect $u$ from $v$, i.e., the nodes on the path that connect $u$ to $v$ (We assume that deleting $u$ will disconnect $u$ from $v$). This can be verified in $\mathcal{O}(n)$ queries as well by iterating over all nodes once.

• Repeat steps 2 and 3 till you find the desired leaf node.

The probability that a random node is a leaf node and is of a different colour than $u$ is $\ge 0.25$. Hence the expected number of queries asked in this algorithm is also $\mathcal{O}(n)$.

Now that we have our two leaf nodes of different colours, we are ready to make the final observation, i.e., the root node must be one of the $2k-1$ nodes that can disconnect $u$ from $v$. Thus there are $2k-1 = \mathcal{O}(\log{n})$ candidates for the root node. We can iterate through each of them and check if they are the root using Routine 1.

Thus this algorithm uses $\mathcal{O}(n\log n)$ queries.

EDIT The final step can be improved to $\mathcal{O}(\log^2{n})$ by running Routine 1 on just the $2k-1$ candidates to find the node that splits the path from $u$ to $v$ into two equal connected components. Thus the problem can be solved in $\mathcal{O}(n)$ queries as well.

StackExchange Computer Science Q#91816, answer score: 3