3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

  1. Let the node to check be $x$.
  2. Pick another node $y \not= x$
  3. Iterate through all other nodes $z \not\in \{x,y\}$ and ask if $x$ disconnects $y$ from $z$.
  4. 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 -

  1. Pick a random node in the tree, say $x$.
  2. Pick another random node $y$.
  3. If $x$ does not disconnect $y$ from $z$, for all valid $z$, then $x$ is a leaf node in the tree.
  4. 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 -

  1. Find any leaf node using the algorithm in Routine 2. Call this leaf node $u$.
  2. Find a different leaf node, call this $v$.
  3. $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.
  4. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.