11institutetext: United World College of South East Asia, Singapore
22institutetext: Amlgo Labs

# Efficient Algorithms for Sorting in Trees

Jishnu Roychoudhury 11 Jatin Yadav 22

(January 2022)

###### Abstract

Sorting is a foundational problem in computer science that is typically
employed on sequences or total orders. More recently, a more general form of
sorting on partially ordered sets (or posets), where some pairs of elements
are incomparable, has been studied. General poset sorting algorithms have a
lower-bound query complexity of $\Omega(wn+n\log n)$, where $w$ is the width
of the poset.

We consider the problem of sorting in trees, a particular case of partial
orders, and parametrize the complexity with respect to $d$, the maximum degree
of an element in the tree, as $d$ is usually much smaller than $w$ in trees.
For example, in complete binary trees, $d=\Theta(1),w=\Theta(n)$. We present a
randomized algorithm for sorting a tree poset in worst-case expected $O(dn\log
n)$ query and time complexity. This improves the previous upper bound of
$O(dn\log^{2}n)$. Our algorithm is the first to be optimal for bounded-degree
trees. We also provide a new lower bound of $\Omega(dn+n\log n)$ for the
worst-case query complexity of sorting a tree poset. Finally, we present the
first deterministic algorithm for sorting tree posets that has lower total
complexity than existing algorithms for sorting general partial orders.

##  1 Introduction

Sorting is a foundational problem in computer science that is typically
employed on a set or multi-set of elements. Given an input set $S$ of $n$
elements, typical sorting problems determine the underlying total order or
linear sequence of the elements. These algorithms assume that the elements are
drawn from an ordered domain (such as the domain of integers). Most sorting
algorithm use comparisons in which direct comparisons between pairs of
elements allows the algorithms to acquire information about the total order
[8]. Some recent works consider a restricted version of standard comparison
sorting where only a subset of pairs are allowed to be compared [3, 4, 12,
14].

More recently, a more general form of sorting on partially ordered sets (or
posets), where some pairs of elements are incomparable, has been studied [2,
5, 6, 9, 10]. Given a input set $P$ of $n$ elements, poset sorting algorithms
determine the underlying partial order of the elements. Sorting problems are
inherently more challenging for partial orders compared to total orders.
Sorting algorithms are generally evaluated by two complexity measures: the
query complexity, the number of comparisons involved, and total complexity,
the total number of computational operations involved. As each individual
query can potentially be quite expensive (for example, requiring physical
experiments), query complexity is equally important as total complexity.
Faigle and Turán were the first to consider the problem of sorting partial
orders [10], providing an algorithm with $O(wn\log n)$ query complexity, where
$n$ is the number of elements and $w$ is the width of the poset. Daskalakis et
al. [9] improved on this result to present an algorithm with optimal query
complexity $O(wn+n\log n)$, and provided a separate algorithm with time
complexity $O(w^{2}n\log\frac{n}{w})$.

Our work is the first to consider sorting tree posets, a particular case of
partial orders. In a tree, the value of $w$ is typically very high, leading to
existing poset sorting algorithms performing poorly. Therefore, it is
important to design efficient customized algorithms for sorting in tree posets
with lower query and total complexity. We instead consider the parameter $d$,
the maximum out-degree of a node in the natural arborescence representation of
the tree. In contrast to width $w$, the degree $d$ is typically much smaller;
for example, $d=\Theta(1),w=\Theta(n)$ in complete binary trees.

Apart from the theoretical significance of the problem, there are many
practical applications, for example, constructing the evolutionary tree of
coronavirus strains or general phylogenetic trees, network mapping, among
others. In addition, the final sorted tree can be used as input for tree
searching algorithms, such as [11, 15]. Onak and Parys [15] considered
extending the concept of binary search to trees, whereas Heeringa, Iordan, and
Lewis [11] considered searching in dynamic trees.

The most similar work to ours is by Wang and Honorio [16], in which the
authors show how to reconstruct a directed tree with $n$ elements and node
degree of at most $d$ using path queries. Afshar et al. [1] studied the
parallel query complexity of reconstructing binary trees from simple queries
involving their nodes. Although [16] does not consider the problem of sorting
a tree poset, the problem they consider can be formulated as a constrained
version of tree poset sorting. A key difference is that in [16], a bound on
node degree $d$ is given as an input. In our problem formulation, the maximum
degree $d$ is not known as an input and instead is discovered by the algorithm
itself. This flexibility significantly improves the applicability of the
solution. We only use $d$ as a parameter in complexity analysis. Wang and
Honorio provide in their paper a randomized algorithm with query complexity
$O(dn\log^{2}n)$, given $d$ as an input, and prove lower bounds of
$\Omega(dn)$ for the query complexity of any deterministic algorithm and
$\Omega(n\log n)$ for the query complexity of any randomized algorithm. We
provide a randomized algorithm with query and time complexity $O(dn\log n)$
for sorting a tree poset without a priori knowledge of $d$. This result is
optimal for trees of bounded degree, such as binary trees. Our randomized
algorithm is unrelated to the algorithm presented in [16] and utilizes a novel
technique based on divide and conquer on the centroid of the tree and random
sampling of elements. We also improve the lower bounds for randomized and
deterministic algorithms to $\Omega(dn+n\log n)$. Therefore, we improve the
gap from $O(d\log^{2}n)$ to $O(\log n)$. Finally, we present the first
deterministic algorithm for sorting tree posets that has a lower time
complexity than existing algorithms for sorting general partial orders.

##  2 Preliminaries

We present the formal definitions for the concepts related to posets, tree
posets, and sorting in posets. We also repeatedly use certain concepts related
to graph-theoretic trees, such as children, edges, degree, and root. In these
cases, we use the same terms as graph-theoretic trees and formally define the
concepts in terms of set theory here for consistency.

######  Definition 1 (poset)

A partially ordered set or poset $\mathcal{P}=(P,\succ)$ is a set of elements
$P$ together with a binary relation $\succ\;\subset P\times P$ which is
irreflexive, transitive, and antisymmetric.

For a pair $(a,b)\in\ \succ$, we write $a\succ b$ and state that $a$ dominates
$b$, or $b$ is dominated by $a$.

######  Definition 2 (tree)

A tree is a poset $\tau=(T,\succ)$ where for all elements $t\in T$, the set of
ancestors of $t$ in the tree, $Anc_{t}=\\{s\in T:s\succ t\\}$, is well-ordered
by the relation $\succ$.

######  Definition 3 (maximal element)

In a poset $\mathcal{P}=(P,\succ)$, an element $x\in P$ is a maximal element
if the set $\\{y\in P:y\succ x\\}$ is empty. The set $M_{\mathcal{P}}$ is the
set of maximal elements in $\mathcal{P}$. We may also refer to a maximal
element as a _root_.

Also, we define an element $e\in S$ to be a maximal element of a set $S$ for
some $S\subseteq T$ if $e$ is a maximal element of
$\mathcal{S}=(S,\succ\cap\>(S\times S))$.

######  Definition 4 (parent, child)

In a tree $\tau=(T,\succ)$, a child of an element $x\in T$ is an element $y\in
T$ such that $x\succ y$ and the set $\\{z\in T:x\succ z\succ y\\}$ is empty.
For an element $t\in T$, we define $ch_{t}$ to be the set of children of $t$.
The parent of an element $x\in T\setminus M_{\tau}$ is an element $y\in T$
such that $y\succ x$ and the set $\\{z\in T:y\succ z\succ x\\}$ is empty. We
denote this parent as $par_{x}$.

We note that, for any $y\in ch_{x}$, $par_{y}=x$, and that every element has a
single parent, except maximal elements, which have no parent.

######  Definition 5 (edge)

The set of edges for a tree $\tau=(T,\succ)$ is
$E_{\tau}=\\{(a,b)\in\succ:b\in ch_{a}\\}$. Any pair $(a,b)\in E$ is referred
to as an edge. There are $|T|-1$ edges in a tree with a single maximal
element.

######  Definition 6 (degree)

In a tree $\tau=(T,\succ)$, we define the degree of an element $t\in T$,
$deg_{t}$, as the number of children of $t$. We define the maximum degree of
the tree, $d(\tau)=\max(|M_{\tau}|,\max_{t\in T}deg_{t})$.

Throughout our paper, we simply use $d$ to denote $d(\tau)$, as for the
problem we deal with, the tree $\tau$ is fixed (but unknown).

For simplicity, we only consider trees with one maximal element in the rest of
this paper. We can easily modify any tree to have one maximal element. Say the
elements of the tree are $\\{t_{1},t_{2},\dots,t_{n}\\}$. We introduce a new
element $t_{n+1}$, such that $t_{n+1}\succ t_{i}$ for all
$i\in\\{1,\dots,n\\}$, and sort the modified tree. We never need to make a
query involving $t_{n+1}$ as it is known that $t_{n+1}$ dominates all other
elements.

######  Definition 7 (descendants)

The set of descendants of an element $t$ is $Desc_{t}=\\{s\in T:t\succ s\\}$.
The subtree of an element $t$ is $Sub_{t}=\\{t\\}\cup Desc_{t}$.

######  Definition 8 (poset width)

In a poset $\mathcal{P}$, an antichain $A\subseteq P$ is a subset of mutually
incomparable elements. The width $w(\mathcal{P})$ of the poset is the maximum
cardinality antichain of the poset $\mathcal{P}$. It should be noted that in a
tree, $w(\tau)$ is equal to the cardinality of the set of minimal elements in
$T$.

Similar to the case for maximum degree, throughout this paper we use $w$ to
denote $w(\mathcal{P})$ as for the problems we deal with, the poset
$\mathcal{P}$ is fixed.

Next, we define the oracle we use for queries before defining the sorting
problem on posets and trees.

######  Definition 9 (comparison oracle)

A comparison query $\mathcal{Q}$ for a poset $\mathcal{P}=(P,\succ)$ is a
function $\mathcal{Q}_{\mathcal{P}}:P\times P\rightarrow\\{\succ,\prec,||\\}$
such that

$\mathcal{Q}_{\mathcal{P}}(i,j)=\left\\{\begin{array}[]{ll}\succ\;\text{if}\;\;i\succ
j\\\ \prec\;\text{if}\;\;j\succ i\\\ ||\;\;\text{otherwise}\end{array}\right.$

The comparison oracle $\mathcal{O}_{\mathcal{P}}$ responds to comparison
queries in $O(1)$ time per query.

For simplicity, we use $\mathcal{Q}$ to denote $\mathcal{Q}_{\mathcal{P}}$ and
$\mathcal{O}$ to denote $\mathcal{O}_{\mathcal{P}}$ throughout this paper. We
note that since a tree is also a poset, our definitions of $\mathcal{Q}$ and
$\mathcal{O}$ apply for trees as well. We use $||$ to denote incomparability.

###### Definition 10

The sorting problem for a poset $\mathcal{P}$ is defined as follows. Given a
set of elements $P$, the information that $\mathcal{P}=(P,\succ)$ is a poset,
and a comparison oracle $\mathcal{O}_{\mathcal{P}}$, construct a data
structure that can correctly respond to comparison queries in $O(1)$ time
without using the oracle $\mathcal{O}_{\mathcal{P}}$.

This definition of the problem was also (implicitly) used in the paper [9].
Essentially, the sorting problem for a poset attempts to reconstruct the
binary relation $\succ$ through a minimal number of queries to a comparison
oracle. As $|\succ|$ may be large (on the order of $n^{2}$), we require the
sorting algorithm to derive only a compact representation of $\succ$ that,
when fully constructed, can be queried in $O(1)$ time. This is similar to the
classical sorting problem, where the algorithm constructs a linear sequence
corresponding to the total order rather than finding the relation between
every pair of elements. The indices of two elements in the linear sequence can
be used to respond to comparison queries in $O(1)$ time.

We now define the sorting problem for trees analogously.

###### Definition 11

The sorting problem for a tree $\tau$ is defined as follows. Given a set of
elements $T$, the information that $\tau=(T,\succ)$ is a tree, and a
comparison oracle $\mathcal{O}_{\tau}$, construct a data structure that can
correctly respond to comparison queries in $O(1)$ time without using the
oracle $\mathcal{O}_{\tau}$.

Our strategy for sorting a tree $\tau$ of $n$ elements consists of two stages:
first, to find the $n-1$ edges of the tree, and second, to use this
information to construct a data structure that can respond to comparison
queries in $O(1)$ time. The second stage can be performed using depth-first
search. We briefly describe it here and the pseudocode is included in Appendix
0.B.

We run a depth-first search of the tree from the root in $O(n)$ time. We let
$s_{v}$ denote the start time of the element $v$ in the depth-first search,
and $e_{v}$ the end time. We note that $u\succ v$ iff $s_{u}\leq s_{v}\leq
e_{v}\leq e_{u}$. Therefore, we can answer comparison queries in $O(1)$ time.

For the remainder of this paper, we focus on finding the edges of $\tau$, as
that is sufficient to sort $\tau$.

##  3 Upper Bounds

###### Theorem 3.1

There is a randomized algorithm which sorts a tree of $n$ elements and maximum
degree $d$ in $O(dn\log{n})$ expected worst-case query and time complexity.

Note that time complexity supersedes query complexity as each query itself
takes constant time. Therefore, we will prove that the time complexity of our
algorithm is $O(dn\log n)$. We will begin by describing an algorithm with a
time complexity of $O(dn\log n+n\log^{2}n)$. Then, we will reduce the
complexity to $O(dn\log n)$ by making use of estimations based on random
sampling, instead of considering all the elements of the tree.

##  4 An $O(dn\log n+n\log^{2}n)$ algorithm

Our algorithm relies on finding a good separating element in the tree and then
dividing the tree into disjoint sub-problems around this element, such that no
sub-problem has a large size. In this section, we use the centroid of the tree
as the separating element.

######  Definition 12 (Centroid)

The centroid of a tree $\tau$ with $n$ elements is an element $c$ such that
the subtree size of $c$, $|Sub_{c}|\geq\frac{n}{2}$, but for all $x\in
ch_{c}$, $|Sub_{x}|<\frac{n}{2}$.

###### Lemma 1

The centroid exists and is unique.

###### Proof

Consider the following algorithm. We start at the root, and keep recursing to
the child with subtree size $\geq\frac{n}{2}$ until there is no such child.
This maintains the invariant that any centroid must be inside the subtree of
the current element. This process must terminate as the number of elements is
finite, and it can only terminate on a centroid (let it be $c$). Any other
centroid must lie in the subtree of $c$, but all children of $c$ have subtree
sizes less than $\frac{n}{2}$, so $c$ must be the only centroid.

###  4.1 Algorithm Outline

Following is a brief outline of our algorithm for sorting a tree of $n$
elements and maximum degree $d$ in $O(dn\log n+n\log^{2}n)$ time. The detailed
pseudocode of the algorithm, GET-EDGES, appears later.

  1. 1.

Choose a random element $x$ and sort the list of its ancestors.

  2. 2.

Binary search on this list to find the minimal element $c$ whose subtree has
size at least $\frac{n}{2}$.

  3. 3.

If $c$ is the centroid continue to step 4, else go back to step 2.

  4. 4.

Divide the elements of the tree (except $c$) into $|ch_{c}|+1$ subproblems.
The subtree of each child of $c$ forms a subproblem and all the remaining
elements of the tree except the subtree of $c$ form an additional subproblem.

  5. 5.

Solve the sorting problem recursively for each subproblem.

  6. 6.

Add the edges from $c$ to its children, and add an edge from the parent of $c$
(if any) to $c$.

###  4.2 Algorithm Details and Complexity Analysis

Our algorithm is given the initial set of elements, $T$, and a comparison
oracle $\mathcal{O}$ for the tree $\tau=(T,\succ)$. Note that when we are
solving a subproblem on a subset $H\subseteq T$ of elements, all of the terms
defined in Section 2 should be considered with respect to the tree
$\tau^{\prime}=(H,\succ\cap\>(H\times H))$, and, in addition, we use $n=|H|$.

Let us first define some subroutines, all of which make use of the oracle
$\mathcal{O}$. We start with GET-ROOT, an algorithm for finding a maximal
element in a set of elements $H\subseteq T$. Suppose we have a set $S$ and a
maximal element $x\in S$. When we add element $e$ to $S$, there are two
possibilities:

  * •

$e\succ x$: $e$ must be a maximal element of $S\cup\\{e\\}$.

  * •

Otherwise, $x$ is also a maximal element of $S\cup\\{e\\}$.

This gives us an algorithm to find a maximal element of any set $H$ in $O(n)$
time. We initialise $S$ to a single element and iteratively add the remaining
elements of $H$ to $S$ while maintaining a maximal element of $S$.

1

2GET-ROOT;

Input : A set $H\subseteq T$

Output : A maximal element of $H$

3 Let $H=\\{h_{1},h_{2},\ldots h_{n}\\}$

4 $x\leftarrow h_{1}$

5 for  _$i=2,\ldots n$_ do

6 if  _$h_{i}\succ x$_ then

7 $x\leftarrow h_{i}$

8 end if

9

10 end for

return _x_

We now define the algorithm GET-SUBTREES-OF-CHILDREN, which finds the subtrees
of the children of a given element $r$ within the tree. This algorithm is used
to test whether a given element is the centroid, as well as to divide the tree
into subproblems around the centroid.

GET-SUBTREES-OF-CHILDREN works as follows. We start by initialising
$S\leftarrow Desc_{r}$. We then repeatedly find a maximal element of $S$ by
calling GET-ROOT, append its subtree to the output, and remove its subtree
from $S$. We repeat until $S=\emptyset$.

1

2GET-SUBTREES-OF-CHILDREN;

Input : A set $H\subseteq T$ having exactly one maximal element, and an
element $r\in H$

Output : List of subtrees of the children of $r$

3 $S\leftarrow\\{x\in H:r\succ x\\}$

4 $C\leftarrow[]$ // An empty list

5 while  _$S\neq\emptyset$_ do

6 $x\leftarrow$ GET-ROOT($S$)

7 $X\leftarrow\\{x\\}\cup\\{y\in S\;|\;x\succ y\\}$

8 Append $X$ to $C$

9 $S\leftarrow S\setminus X$

10 end while

return _C_

###### Lemma 2

The algorithm GET-SUBTREES-OF-CHILDREN correctly outputs all the subtrees of
the children of a given element $r$ in $O(dn)$ time.

###### Proof

It is clear that each iteration of lines 5 to 8 takes $O(n)$ time. Moreover,
the maximal element we find in each iteration is always a child of $r$, and
there are at most $d$ such elements; thus, we make at most $d$ iterations.
Therefore, the total time complexity is $O(dn)$.

We can test whether an element is a centroid by first finding its subtree in
$O(n)$ time and then finding the subtrees of all its children in $O(dn)$ time
using GET-SUBTREES-OF-CHILDREN.

We are now ready to describe the algorithm GET-CENTROID for finding the
centroid of a tree. GET-CENTROID starts by taking a random element $t$ from
the tree and finding the list of ancestors of $t$, $Anc_{t}$. The list
$Anc_{t}$ is well-ordered by definition, so it may be sorted using a typical
$O(n\log n)$ algorithm for sorting a total order. The algorithm then binary
searches to find the minimal element $y\in Anc_{t}\cup\\{t\\}$ which satisfies
$|Sub_{y}|\geq\frac{n}{2}$. The algorithm finally checks if $y$ is the
centroid: if so, it terminates, and otherwise it repeats from the beginning
until it finds a centroid.

1

2GET-CENTROID;

Input : A set $H\subseteq T$ which has exactly one maximal element

Output : The centroid of the tree $(H,\succ\cap\>(H\times H))$

3 $n\leftarrow|H|$

4 Choose a random element $t$ from $H$

5 while  _$t$ is not the centroid_ do

6 Choose a random element $x$ from $H$

7 $Y\leftarrow\\{x\\}\cup\\{y\in H\>|\>y\succ x\\}$

8 Sort $Y$ according to the order relation $\succ$ /*$Y$ is well ordered by
definition*/

9 Let $Y=\\{y_{1},y_{2},\ldots y_{k}\\}$ where $y_{1}\succ y_{2}\succ\ldots
y_{k-1}\succ y_{k}$

10 Binary search on the largest $i$, such that the subtree size of $y_{i}$ is
$\geq n/2$.

11 $t\leftarrow y_{i}$

12 end while

13

return _$t$_

###### Lemma 3

The algorithm GET-CENTROID finds the centroid in $O(dn+n\log n)$ expected
time.

###### Proof

It is easy to see that every iteration of lines $4$ to $10$ takes $O(dn+n\log
n)$ time. The sorting of the set $Y$ takes $O(n\log n)$ time and testing
whether $t$ is a centroid takes $O(dn)$ time. In addition, in each step of the
binary search of line 9 we find the subtree size of some element, which uses
$O(n)$ time. Since there are $O(\log n)$ steps of binary search, line 9 uses
$O(n\log n)$ time overall. Everything else takes $O(n)$ time in total.

Let the centroid be $c$. With probability at least $\frac{1}{2},c=x$ or
$c\succ x$. This is because the subtree size of $c$ is greater than or equal
to $\frac{n}{2}$ by definition, and $x$ is chosen uniformly at random out of
the $n$ elements. When this happens, $c\in Y$ and the binary search returns
$y_{i}=c$, as the subtree sizes for the descendants of $c$ are less than
$\frac{n}{2}$. Hence, with probability at least $\frac{1}{2}$ we find the
centroid. Thus, the expected number of iterations is less than or equal to
$2$, and we get the centroid in $O(dn+n\log n)$ expected time.

We now present the pseudocode for the overall algorithm GET-EDGES, which was
outlined previously in Subsection 4.1.

1

2GET-EDGES;

Input : A set $H\subseteq T$ which is either empty or has exactly one maximal
element

Output : The set of the $|H|-1$ edges of $(H,\succ\cap\>(H\times H))$

3 $n\leftarrow|H|$

4 if  _$n\leq 1$_ then

5 return _$\\{\\}$_

6 end if

7$c\leftarrow$ GET-CENTROID($H$)

8 $\chi\leftarrow$ GET-SUBTREES-OF-CHILDREN($H$, $c$)

9 $C\leftarrow\\{c\\}\cup\\{x\in H\>|\>c\succ x\\}$

10 $Y\leftarrow H\setminus C$

11 $E\leftarrow$ GET-EDGES($Y$)

12 for  _$X\in\chi$_ do

13 $E\leftarrow E\>\cup$ GET-EDGES($X$)

14 $E\leftarrow E\cup\\{(c,\texttt{GET-ROOT}($X$))\\}$

15 end for

16if  _$Y\neq\emptyset$_ then

17 $p=\min\\{y\in Y\>|\>y\succ c\\}$ /* $\min$ is defined, as the set of
ancestors is well ordered */

18 $E\leftarrow E\cup\\{(p,c)\\}$

19 end if

return _$E$_

###### Lemma 4

The algorithm GET-EDGES(H) correctly outputs the edges of $H$ in worst case
expected $O(dn\log n+n\log^{2}n)$ time.

###### Proof

Our algorithm first finds the edges inside the subtree of the centroid $c$ by
recursively calling GET-EDGES and adding $(c,x)$ to the list of edges for
every child $x$ of $c$. After this, we add the edges that are outside the
subtree. Finally, we add the edge between $c$ and its parent if it exists.
Clearly, the algorithm is correct as it returns all the edges.

Let $Q_{d}(n)$ be the expected time needed by the algorithm in the worst case
(the maximum expected value over all different trees with $n$ elements and
maximum degree $\leq d$).

Note that every sub-problem is either a subtree of a child of $c$, which by
definition has a size $<\frac{n}{2}$, or is equal to $H\setminus C$, where $C$
is the subtree of $c$. As $|C|\geq\frac{n}{2}$, all sub-problems have sizes
$\leq\frac{n}{2}$. Also, note that all sub-problems also have degree $\leq d$.

It takes $O(dn+n\log n)$ expected time to get the centroid. Then, we divide
into sub-problems by calling GET-SUBTREES-OF-CHILDREN in $O(dn)$. All other
steps are done in $O(n)$ total. Thus, it takes $O(dn+n\log n)$ expected time
to get the division into sub-problems. Moreover, the function $f(n)=dn+n\log
n$ satisfies $f(u)\geq 0,f(u)+f(v)\leq f(u+v)$ for all $u,v\geq 1$. Using
Theorem 0.A.1, the overall time complexity is $Q_{d}(n)=O((dn+n\log n)\log n)$
= $O(dn\log n+n\log^{2}n)$.

##  5 Optimizing to $O(dn\log n)$

We want to decrease the complexity of GET-CENTROID from $O(dn+n\log n)$ to
$O(dn)$. In our solution, one part of this optimization is to use random
sampling to find estimated subtree sizes in $(\frac{n}{\log n})$, instead of
finding exact sizes in $O(n)$. In this process, we might not get the centroid
from the binary search because of errors in subtree size computation, but we
prove that, with a constant lower bound on probability, we get another form of
a good separator, which we term a pseudo-centroid.

######  Definition 13 (Pseudo-Centroid)

A pseudo-centroid of a tree $\tau=(T,\succ)$ is an element $c$, for which the
size of subtree of $c$ is $\geq\frac{n}{4}$, and for any of its children, the
size of subtree is $<\frac{n}{2}$. In particular, note that the centroid is
also a pseudo-centroid.

It is clear that, if we replace the centroid by a pseudo-centroid in the
previous algorithm, all the sub-problem sizes are less than or equal to
$\frac{3n}{4}$. It turns out that we can find a pseudo-centroid in expected
$O(n)$ time using sampling, and this removes $O(n\log n)$ from the complexity
of GET-CENTROID. We assume sufficiently large $n$ (greater than some constant)
in the discussion to follow to avoid minor details such as the possibilities
of $\log n=0$ or $\frac{1}{\log n}>1$, and for some inequalities to be true.

Let $p=\frac{1}{\log n}$. For finding a pseudo-centroid efficiently, we make
the following changes:

  1. 1.

We do not find the exact subtree size when binary searching. Instead, we first
randomly sample a subset $V$ of $H$ by adding each element of $H$ to $V$ with
an independent probability of $p$. Let’s define $S_{i}$ to be the size of the
subtree of element $i$. Now, we define the sampled subtree size,
$F^{\prime}_{i}$ to be the number of sampled elements that lie inside the
subtree of $i$. Clearly $\mathbb{E}(F^{\prime}_{i})=S_{i}p$. Also, we define
the estimated subtree size of $i$ to be
$S^{\prime}_{i}=\frac{F^{\prime}_{i}}{p}$, so that
$\mathbb{E}(S^{\prime}_{i})=S_{i}$. This reduces the the time taken in subtree
size computation by a factor of $\log n$.

  2. 2.

Now, we will return the minimal element in $Y$ whose estimated subtree size is
greater than or equal to $\frac{n}{2}-\frac{1}{p}$. Here, two things have
changed: we are using estimated subtree size instead of subtree size, and we
now have $\frac{n}{2}-\frac{1}{p}$ as the threshold as opposed to
$\frac{n}{2}$ before. Note that the monotonicity is still maintained, i.e. the
estimated subtree size of a child will not be greater than that of its parent.
So, we can still perform binary search to do this step.

  3. 3.

We do not sort the whole chain of ancestors $Y$, which earlier lead to a
sorting overhead of $O(n\log n)$. Instead, we first randomly sample a subset
$Z$ of $Y$ by adding each element of $Y$ to $Z$ with an independent
probability of $p$, and then sort $Z$. Since
$\mathbb{E}(|Z|)=\frac{\mathbb{E}(|Y|)}{\log n}$, the expected sorting
overhead is now $O(n)$.

  4. 4.

We perform the binary search in two phases:

    1. (a)

Binary search to find the position of the estimated centroid within $Z$.

    2. (b)

Find the position within the expected $O(\log n)$ elements that lie in-between
this element and the immediate next(if any) in $Z$

Once we have found the pseudo-centroid, the rest of the algorithm remains the
same as before.

1

2GET-PSEUDO-CENTROID;

Input : A set $H\subseteq T$ having exactly one maximal element

Output : A pseudo centroid of $(H,\succ\cap\>(H\times H))$

3 $n\leftarrow|H|$

4 Choose a random element $t$ from $H$

5 while  _$t$ is not a pseudo-centroid_ do

6 $p\leftarrow\ \frac{1}{\log n}$

7 $V\leftarrow\\{\\}$

8

9 for  _$i\in H$_ do

10 Add $i$ to $V$ with probability $p$

11 end for

12

13 Choose a random element $x$ from $H$.

14

15 $Y\leftarrow\\{x\\}\cup\\{y\in H\>|\>y\succ x\\}$

16

17 $Z\leftarrow\\{\texttt{GET-ROOT}(H)\\}$

18

19 for  _$i\in Y$_ do

20 Add $i$ to $Z$ with probability $p$

21 end for

22

23 Sort $Z$ according to the order relation $\succ$

24

25 Let $Z=\\{z_{1},z_{2},\ldots z_{k}\\}$ where $z_{1}\succ z_{2}\succ\ldots
z_{k-1}\succ z_{k}$

26

27 Define $S^{\prime}_{j}$ to be the estimated size of subtree of $j$,
$S^{\prime}_{j}=\dfrac{|(\\{j\\}\cup\\{i\in H|j\succ i\\})\cap V|}{p}$

28

29 if  _$S^{\prime}_{z_{1}}\geq\frac{n}{2}-\frac{1}{p}$_ then

30 Binary search to find the largest $i$, such that
$S^{\prime}_{z_{i}}\geq\frac{n}{2}-\frac{1}{p}$

31

32 $L\leftarrow\\{z_{i}\\}$

33

34 for  _$u\in Y$_ do

35 if  _( $i\neq k$ and $z_{i}\succ u$ and $u\succ z_{i+1}$) or ($i=k$ and
$z_{i}\succ u$)_ then

36 $L\leftarrow L\cup\\{u\\}$

37 end if

38

39 end for

40 Sort $L$ according to the order relation $\succ$

41

42 Let $L=\\{l_{1},l_{2},\ldots,l_{r}\\}$, where $l_{1}\succ l_{2}\ldots
l_{r-1}\succ l_{r}$

43

44 Binary search to find the largest $i$, such that
$S^{\prime}_{l_{i}}\geq\frac{n}{2}-\frac{1}{p}$

45 $t\leftarrow l_{i}$

46 end if

47

48 end while

return _$t$_

###### Lemma 5

The algorithm GET-PSEUDO-CENTROID finds a pseudo-centroid in $O(dn)$ expected
time.

###### Proof

Let the centroid be $c$ (this is the unique centroid, not just a pseudo-
centroid). We first prove that, for sufficiently large $n$, if all of the
following three events occur in an iteration of our algorithm, we get a
pseudo-centroid.

  1. 1.

$x=c$ or $c\succ x$

  2. 2.

$S^{\prime}_{c}\geq\frac{n}{2}-\frac{1}{p}$

  3. 3.

For all $i\in T$, $S^{\prime}_{i}\leq S_{i}+\frac{n}{10}$

Assume the iteration returns $c^{\prime}$. If $c^{\prime}=c$, we are done.
Else, $c\succ c^{\prime}$. Now,
$S^{\prime}_{c^{\prime}}\geq\frac{n}{2}-\frac{1}{p}$ (as the binary search
returns $c^{\prime}$) and $S_{c^{\prime}}\geq
S^{\prime}_{c^{\prime}}-\frac{n}{10}$ (event 2). Adding these two gives
$S_{c^{\prime}}\geq\frac{n}{2}-\frac{1}{p}-\frac{n}{10}=\frac{2n}{5}-\log
n\geq\frac{n}{4}$ for sufficiently large $n$. Also,
$S_{c^{\prime}}<\frac{n}{2}$ as $c^{\prime}$ lies strictly inside the subtree
of $c$, and all children of $c$ have sizes $<\frac{n}{2}$. So, for every child
$r$ of $c^{\prime}$, $S_{r}<S_{c^{\prime}}<\frac{n}{2}$. Thus, $c^{\prime}$ is
a pseudo-centroid.

We will prove that the probability of these 3 events all happening
simultaneously is $\geq\frac{1}{8}$ for sufficiently large $n$. So, let us try
to get an upper bound on at least one of these not happening. Let
$p_{1},p_{2},p_{3}$ be the probabilities of events $1,2,3$ not happening
respectively. We will establish bounds on all three of them.
$\mathbf{p_{1}\leq\frac{1}{2}}$ has already been proved before.

To get an upper bound on $p_{2}$, note that $F^{\prime}_{c}$ follows a
binomial distribution with parameters $S_{c}\geq\frac{n}{2}$ and
$p=\frac{1}{\log n}$. As any median of a binomial distribution with parameters
$n$ and $p$ is $\geq\lfloor np\rfloor$ [13], we have
$S_{c^{\prime}}=F_{c^{\prime}}/p\geq\lfloor\frac{pn}{2}\rfloor/p\geq\frac{n}{2}-\frac{1}{p}$
with probability atleast $\frac{1}{2}$. Therefore,
$\mathbf{p_{2}\leq\frac{1}{2}}$.

Now, we will prove that $p_{3}\leq\frac{1}{4}$ for sufficiently large $n$.
Indeed, consider an element $i$, with $k$ elements in its subtree,
$u_{1},u_{2},\ldots u_{k}$, where $k=S_{i}$. Let $X_{j}$ be an indicator
variable for whether $u_{j}$ was chosen in $V$. All $X_{j}$’s are independent
and identically distributed with $\mathbb{E}(X_{j})=p$. Also,
$F^{\prime}_{i}=X_{1}+X_{2}+\ldots X_{k}$, and
$\mathbb{E}(F^{\prime}_{i})=kp$. Since we want a total error of
$\leq\frac{np}{10}$ in $F^{\prime}_{i}$, we use the Chernoff bound [7] with
$\mu=kp,\delta=\frac{n}{10k}\geq\frac{1}{10}$ to get:

$\displaystyle\displaystyle\mathbb{P}\left(F^{\prime}_{i}>kp+\dfrac{np}{10}\right)=\mathbb{P}\left(F^{\prime}_{i}>\mu(1+\delta)\right)\leq\exp\left(-\dfrac{\mu}{3}\delta\min(1,\delta)\right)\leq\exp\left(-\dfrac{kp}{3}\dfrac{n}{10k}\dfrac{1}{10}\right)=\exp\left(\dfrac{-np}{300}\right)$

But $F^{\prime}_{i}=pS^{\prime}_{i}$, and $k=S_{i}$. Therefore, for any $i$,

$\displaystyle\displaystyle\mathbb{P}\left(S^{\prime}_{i}>S_{i}+\dfrac{n}{10}\right)=\mathbb{P}\left(F^{\prime}_{i}>kp+\dfrac{np}{10}\right)\leq\exp\left(\dfrac{-np}{300}\right)$

Using the union bound, $p_{3}\leq\displaystyle
n\cdot\exp\left(\dfrac{-np}{300}\right)=n\exp\left(\dfrac{-n}{300\log
n}\right)\leq\frac{1}{4}$ for sufficiently large $n$.

Now, let us say an iteration fails if at least one of the events $1,2,3$ is
false. The probability of failure of an iteration is the sum of the
probability of event $1$ not happening and the probability of event 1
happening but at least one of the events 2 and 3 not happening. Noticing that
event $1$ is independent of both events $2$ and $3$, and applying union
bound,we get that the probability of failure is at max:

$p_{1}+(1-p_{1})(p_{2}+p_{3})\leq
p_{1}+\frac{3}{4}(1-p_{1})=\frac{3}{4}+\frac{p_{1}}{4}\leq\frac{7}{8}$

Therefore, we find a pseudo-centroid with probability $\geq\frac{1}{8}$ in
every iteration, and hence the expected number of iterations is $O(1)$.

We now prove that each iteration takes $O(dn)$ time. We divide the iteration
into its constituent steps to do so.

  1. 1.

Finding $Y$ clearly takes $O(n)$ time.

  2. 2.

Sorting $Z$ takes $O(|Z|\log|Z|$) time, and since
$\mathbb{E}(|Z|)\leq\frac{n}{\log n}$, this also takes $O(n)$ time.

  3. 3.

Finding $S^{\prime}_{j}$ takes expected $\mathbb{E}(|V|)=\frac{n}{\log n}$
time. We find $S^{\prime}_{j}$ $O(\log n)$ times during the binary search, so
the binary search also takes $O(n)$.

  4. 4.

Finding the set $L$ clearly takes $|Y|=O(n)$ time, as for each element in $Y$,
we query whether it is between two given elements of $Z$.

  5. 5.

The expected number of elements in $L$ is $O(\log n)$. This is because the the
output $t$ of an iteration is independent of $Z$ and the size of $L$ is equal
to the number of elements in $Y$ that lie between the element just below and
just above $t$ in $Z$. Hence, the expected size is clearly $O(\log n)$. As a
result, expected time to sort $L$ is $\mathbb{E}(|L|\log|L|)$ =
$O(\mathbb{E}(|L|\log n))$ = $O(\log n\log n)=O(n)$.

  6. 6.

We then binary search on the list $L$. In each step of the binary search, we
find the estimated subtree size of some element, which takes $O(\frac{n}{\log
n})$ time. There are $O(\log n)$ steps, so this step is also $O(n)$.

  7. 7.

Checking whether $t$ is a pseudo-centroid takes $O(dn)$ time, as described
previously.

###### Lemma 6

GET-EDGES-OPTIMIZED sorts a tree using $O(dn\log n)$ expected time

###### Proof

The only difference between GET-EDGES and GET-EDGES-OPTIMIZED is that one uses
GET-CENTROID and the other uses GET-PSEUDO-CENTROID.

Here, each sub-problem has size $\leq\frac{3n}{4}$, and we get the division
into sub-problems using $O(dn)$ expected time. The function $f(n)=dn$
satisfies $f(u)\geq 0,f(u)+f(v)\leq f(u+v)$ for all $u,v\geq 1$. Hence, using
Theorem 0.A.1, the expected time complexity is $Q_{d}(n)=O(dn\log n)$.

1

2GET-EDGES-OPTIMIZED;

Input : A set $H\subseteq T$ which is either empty or has exactly one maximal
element

Output : The set of the $|H|-1$ edges of $(H,\succ\cap\>(H\times H))$

3 $n\leftarrow|H|$

4 if  _$n\leq 1$_ then

5 return _$\\{\\}$_

6 end if

7$c\leftarrow$ GET-PSEUDO-CENTROID($H$)

8 $\chi\leftarrow$ GET-SUBTREES-OF-CHILDREN($H$, $c$)

9 $C\leftarrow\\{c\\}\cup\\{x\in H\>|\>c\succ x\\}$

10 $Y\leftarrow H\setminus C$

11 $E\leftarrow$ GET-EDGES-OPTIMIZED($Y$)

12 for  _$X\in\chi$_ do

13 $E\leftarrow E\>\cup$ GET-EDGES-OPTIMIZED($X$)

14 $E=E\cup\\{(c,\texttt{GET-ROOT}($X$))\\}$

15 end for

16if  _$Y$ is not empty_ then

17 $p=\min\\{y\in Y\;|\;y\succ c\\}$ /* min is defined, as the set of
ancestors is well ordered */

18 $E\leftarrow E\cup\\{(p,c)\\}$

19 end if

return _$E$_

##  6 Deterministic Algorithm

###### Theorem 6.1

There is a deterministic algorithm which sorts a tree of $n$ elements and
width $w$ in $O(wn+n\log n)$ worst-case query and time complexity.

We briefly describe a deterministic algorithm GET-EDGES-DET which runs in
worst-case total complexity of $O(wn+n\log n)$. The pseudocode of the
algorithm is included in Appendix 0.B.

We can find a single minimal element in a set of elements $H\subseteq T$ in
$O(n)$ time by using a procedure similar to GET-ROOT presented earlier. Let
$H=\\{h_{1},h_{2},\dots,h_{n}\\}$. We initialize $x\leftarrow h_{1}$. Then, we
iterate through all other $h_{i}$, setting $x\leftarrow h_{i}$, if $x\succ
h_{i}$. At the end of this procedure, $x$ is a minimal element.

Our algorithm starts with $H=T$. After we find a minimal element $x\in H$, we
can find the set of ancestors of $x$, $Anc_{x}$, in $O(n)$ time. As $Anc_{x}$
is a total order, we can sort it in $O(n\log n)$ time. We may then find the
parent of each element in the chain $R=Anc_{x}\cup\\{x\\}$ except the maximal
element, and add the chain to a chain decomposition $\mathcal{C}$. We set
$H\leftarrow H\setminus R$, and repeat until $H$ is empty.

The preceding method successfully divides the tree $\tau=(T,\succ)$ into
$|\mathcal{C}|$ disjoint chains such that $par_{x}$ is defined for every
element $x$ on a chain except the maximal element. We therefore notice that
there are only $|\mathcal{C}|$ elements for which $par_{x}$ is not defined.
Hence, for each of these elements $e$, we use $O(n)$ time to find the minimal
element which dominates $e$ (if one exists), which is the parent of $e$.

Finally, for all elements $t\in T$, we construct the edge $(par_{t},t)$ if $t$
is not a maximal element.

###### Lemma 7

The algorithm GET-EDGES-DET($T$) correctly outputs the edges of $T$ in
$O(wn+n\log n)$ time.

###### Proof

Finding a single minimal element clearly takes $O(n)$ time. Additionally, the
width of $\tau$ is $w$. Therefore, there are exactly $w$ minimal elements in
$T$. We observe that each time we find a minimal element of $H$, said element
is also a minimal element of $T$. This is because, when we remove a chain $C$
from the tree, no element in $H\setminus C$ succeeds an element in $C$.
Therefore, any minimal element in $H\setminus C$ was also a minimal element in
$H$. Thus, we make $w$ iterations, which takes $O(wn)$ time. Moreover,
$|\mathcal{C}|=w$ as a result.

Finding the minimal element which dominates an element $e$ takes $O(n)$ time.
We repeat this $|\mathcal{C}|$ times, once for each chain in the chain
decomposition. Thus, this step also takes $O(wn)$ time. Finally, the total
complexity of sorting all chains is $O(n\log n)$ as the chains are disjoint.
This results in the final time complexity of $O(wn+n\log n)$.

We comment that during our iteration, it is possible that removing elements
causes the tree to have multiple roots. However, note that this does not
affect the correctness or complexity of our algorithm.

##  7 Lower Bounds

###### Theorem 7.1

The worst-case expected query complexity of the tree sorting problem on a tree
of $n$ elements with maximum degree $d$ is $\Omega(dn+n\log n)$.

###### Proof

We consider a tree $\tau=(T,\succ)$ on $n$ elements with the following form.
Let $T=\\{t_{1},\dots,t_{n}\\}$. There is a single maximal element $t_{1}$. In
addition, each element $t_{i}$ ($i>1$) has parent
$t_{d\lfloor(i-2)/d\rfloor+1}$.

We assume that the algorithm has not explicitly queried a pair of elements
$(x,y)$ where $par_{x}=par_{y}=p$ and $|ch_{x}|=|ch_{y}|=0$. We consider the
tree $\tau^{\prime}=(T,\succ^{\prime})$ where
$\succ^{\prime}=(\succ\cup\>\\{(x,y)\\})$. In graph-theoretic terms,
$\tau^{\prime}$ is identical to $\tau$ except that the parent of $y$ is $x$
instead of $p$. We note that the answers to queries to $\tau^{\prime}$ are the
same as the answers to queries to $\tau$ except for the query $(x,y)$.
Therefore, the algorithm is unable to distinguish $\tau$ from $\tau^{\prime}$
without explicitly querying $(x,y)$. There are at least
$\lfloor\frac{n-1}{d}\rfloor\binom{d-1}{2}=\Omega(dn)$ unordered pairs $(x,y)$
which satisfy the condition, thus implying a lower bound on the query
complexity of sorting a tree of $\Omega(dn)$.

Sorting a total order has an average case query complexity of $\Omega(n\log
n)$ [8]. Since a total order is a tree with maximum degree $1$, this also
implies a lower bound of $\Omega(n\log n)$ for the query complexity of sorting
a tree. Combining this result with the previous result gives the lower bound
of $\Omega(dn+n\log n)$.

We note that this proof holds for any Las Vegas randomized algorithm as well
as deterministic algorithms, since we provide an explicit minimal set of
queries which the algorithm is required to make. If any query in this set is
not made, the algorithm cannot determine the correct answer with probability
$1$.

We now consider a more fundamental problem of recognizing whether a given
poset is a tree poset by asking comparision queries. We prove the lower bound
of $\Omega(n^{2})$ for this problem.

###### Theorem 7.2

The expected worst-case query complexity of recoginizing whether a given poset
$\tau=(T,\succ)$ is a tree is $\Omega(n^{2})$

###### Proof

We consider the same tree $\tau$ as used for the proof of Theorem 7.1, with
$d=2$. Let $L$ be the set of minimal elements of $\tau$. Note that
$|L|=\Theta(n)$. We assume that the algorithm has not explicitly queried a
pair of elements $(x,y)$ where $x\in L,y\in L,|Anc_{x}|<|Anc_{y}|$. Note that
this implies $Anc_{x}\subset Anc_{y}$ according to the structure of our tree.
We consider $\tau^{\prime}=(T,\succ^{\prime})$ where
$\succ^{\prime}=(\succ\cup\>\\{(x,y)\\})$ and prove that $\tau^{\prime}$ is a
poset.

Note that all properties of a poset are immediately satisfied except
transitivity. Assume that $\succ^{\prime}$ is not transitive. Say
$a\succ^{\prime}b\succ^{\prime}c$, but $(a,c)\notin\>\succ^{\prime}$. Note
that either $(a,b)=(x,y)$, or $(b,c)=(x,y)$, else $(a,b)$ and $(b,c)$ were
also in $\succ$, implying $(a,c)\in\>\succ$, and hence
$(a,c)\in\>\succ^{\prime}$. Also, $(a,b)\neq(x,y)$, as $y$ is a minimal
element, contradicting $b\succ^{\prime}c$. Thus $(b,c)=(x,y)$, but then $a\in
Anc_{x}\subset Anc_{y}$, meaning $a\succ c$, and hence $a\succ^{\prime}c$,
which contradicts our assumption.

Let $par_{y}=p$ in $\tau$. Clearly, $\tau^{\prime}$ is not a tree because
$p\succ^{\prime}y$ and $x\succ^{\prime}y$, but $p$ and $x$ are incomparable.
We note that the answers of queries to $\tau^{\prime}$ are the same as the
answers to $\tau$ except for the query $(x,y)$. Therefore, the algorithm is
unable to distinguish $\tau$ from $\tau^{\prime}$. Since $\tau$ is a tree and
$\tau^{\prime}$ is not a tree, the algorithm is therefore unable to determine
whether the poset described by the oracle is a tree or not without explicitly
querying $(x,y)$. There are at least $\binom{|L|}{2}-1=\Omega(n^{2})$ queries
of this form.

Similar to Theorem 7.1, this proof holds for any Las Vegas randomized
algorithm.

Informally, this result shows that the initial information that $\tau$ is a
tree (and not merely a general poset) is necessary for an algorithm to sort
$\tau$ efficiently.

##  8 Concluding Remarks

In this paper, we have considered the problem of sorting in trees, a
particular case of partial orders. Existing algorithms for sorting in posets
perform poorly in trees because their complexity bounds are dependent on the
width of the partial order, which is expected to be quite large for trees. We
presented a randomized algorithm for sorting a tree poset in worst-case
expected $O(dn\log n)$ query and time complexity, where $d$ is the maximum
degree of the tree. This is optimal for trees of bounded degree. We also
provided a new lower bound of $\Omega(dn+n\log n)$ for the worst-case query
complexity of any randomized or deterministic algorithm for sorting a tree
poset. We presented the first deterministic algorithm for sorting tree posets
with a lower time complexity of $O(wn+n\log n)$ (where $w$ is the width of the
tree) than existing algorithms for sorting general posets. Finally, we showed
that the recognition of a tree poset takes at least quadratic time.

####  8.0.1 Acknowledgements

We would like to thank Diptarka Chakraborty (National University of Singapore)
for providing advice on this work.

## References

  * [1] Ramtin Afshar, Michael T Goodrich, Pedro Matias, and Martha C Osegueda.  Reconstructing binary trees in parallel.  In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pages 491–492, 2020.
  * [2] Ramtin Afshar, Michael T Goodrich, Pedro Matias, and Martha C Osegueda.  Parallel network mapping algorithms.  In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pages 410–413, 2021.
  * [3] Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, and Rafail Ostrovsky.  Matching nuts and bolts.  In SODA, pages 690–696. Citeseer, 1994.
  * [4] Indranil Banerjee and Dana Richards.  Sorting under forbidden comparisons.  In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
  * [5] Arindam Biswas, Varunkumar Jayapaul, and Venkatesh Raman.  Improved bounds for poset sorting in the forbidden-comparison regime.  In Conference on Algorithms and Discrete Applied Mathematics, pages 50–59. Springer, 2017.
  * [6] Jean Cardinal and Samuel Fiorini.  On generalized comparison-based sorting problems.  In Space-Efficient Data Structures, Streams, and Algorithms, pages 164–175. Springer, 2013.
  * [7] Herman Chernoff.  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  The Annals of Mathematical Statistics, pages 493–507, 1952.
  * [8] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2022.
  * [9] C Daskalakis, RM Karp, E Mossel, SJ Riesenfeld, and E Verbin.  Sorting and selection in posets.  SIAM Journal on Computing, 40(3), 2011.
  * [10] U Faigle and Gy Turan.  Sorting and recognition problems for ordered sets.  SIAM Journal on Computing, 17(1), 1988.
  * [11] Brent Heeringa, Marius Cătălin Iordan, and Louis Theran.  Searching in dynamic tree-like partial orders.  In 12th international conference on Algorithms and data structures (WADS), 2011.
  * [12] Zhiyi Huang, Sampath Kannan, and Sanjeev Khanna.  Algorithms for the generalized sorting problem.  In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 738–747. IEEE, 2011.
  * [13] Rob Kaas and Jan M Buhrman.  Mean, median and mode in binomial distributions.  Statistica Neerlandica, 34(1):13–18, 1980.
  * [14] William Kuszmaul and Shyam Narayanan.  Stochastic and worst-case generalized sorting revisited.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1056–1067. IEEE, 2022.
  * [15] K. Onak and P. Parys.  Generalization of binary search: Searching in trees and forest-like partial orders.  In IEEE Symposium on Foundations of Computer Science (FOCS), 2006\.
  * [16] Zhaosen Wang and Jean Honorio.  Reconstructing a bounded-degree directed tree using path queries.  In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 506–513. IEEE, 2019.

##  Appendix 0.A Appendix: Theorems

We present the proof of Theorem 0.A.1, which is used in the complexity
analysis of the algorithms GET-EDGES and GET-EDGES-OPTIMIZED.

###### Theorem 0.A.1

Consider a randomized divide and conquer algorithm, that divides an instance
$I$ of size $n$ into sub-problems of size $\leq cn$ for some constant $0<c<1$
in expected $O(f(n))$ time, such that the sum of sizes of sub-problems is
$\leq n$, for some $f:\mathbb{N}\rightarrow\mathbb{Z}_{\geq 0}$, which
satisfies $f(u)+f(v)\leq f(u+v)$ for all $u,v\geq 1$. The expected worst case
time complexity of the algorithm is $O(f(n)\log n)$

###### Proof

Consider the recursion tree. Every time we divide a problem, the sub-problem
has size $\leq c$ times the parent problem. Thus, there are $O(\log n)$ levels
in the recursion tree. Consider one level. Let the sizes of the problems at
this level be $n_{1},n_{2},\ldots n_{k}$. It is easy to see using induction
that the sum of sizes at any level is $\leq n$. So, let $\sum n_{i}=r\leq n$.
The contribution of this level is then $\sum f(n_{i})\leq\sum
f(n_{i})+f(1)\cdot(n-r)\leq f(n)$ (using $f(u)+f(v)\leq f(u+v)$ for all
$u,v\geq 1$). Therefore, the total complexity is $O(f(n)\log n)$.

##  Appendix 0.B Appendix: Algorithms

We present the pseudocode of algorithms that were not included in the main
body of the paper. We first introduce CONSTRUCT-REPRESENTATION, which takes as
input the edges of $\tau=(T,\succ)$ and returns a data structure of $O(n)$
space which succinctly represents the binary relation $\succ$. CONSTRUCT-
REPRESENTATION makes use of the subroutine DFS.

1

2CONSTRUCT-REPRESENTATION;

Input : A set $T$, an adjacency list $A$ with the outgoing edges from each
element in $T$

Output : A pair of arrays $(s,e)$

3 $t\leftarrow 1$

4 Let $s$ and $e$ be integer arrays of $|T|$ elements

5 Let $V$ be a boolean array of $|T|$ elements

6 Set all elements in $V$ to $0$

7 $r\leftarrow$ GET-ROOT($T$)

8 DFS($r$)

return _$(s,e)$_

1

2DFS;

Global : A set $T$; an adjacency list $A$ with the outgoing edges from each
element in $T$; an integer $t$, initialised to $1$; two integer arrays $s$ and
$e$ of $|T|$ elements; a boolean array $V$ of $|T|$ elements, all initialised
to $0$

Input : A single element $r$

3 $V_{r}\leftarrow 1$

4 $s_{r}\leftarrow t$

5 $t\leftarrow t+1$

6 Let $A_{r}=\\{a_{1},\dots,a_{k}\\}$

7 for  _$i=1,\dots,k$_ do

8 if  _$V_{a_{i}}=0$_ then

9 DFS($a_{i}$)

10 end if

11

12 end for

13$e_{r}\leftarrow t$

14 $t\leftarrow t+1$

We also present COMPARISON-QUERY, which uses the data structure produced by
CONSTRUCT-REPRESENTATION to answer comparison queries in $O(1)$ time per
query.

1

2COMPARISON-QUERY;

Global : Two integer arrays $s$ and $e$

Input : Two elements $u$ and $v$

Output : $\mathcal{Q}(u,v)$

3 if  _$s_{u}\leq s_{v}$ and $e_{v}\leq e_{u}$_ then

4 return _$\succ$_

5 else if  _$s_{v}\leq s_{u}$ and $e_{u}\leq e_{v}$_ then

6 return _$\prec$_

7 else

8 return _$||$_

9 end if

Finally, we present GET-EDGES-DET, which sorts a tree of $n$ elements and
width $w$ in $O(wn+n\log n)$ time.

1

2GET-EDGES-DET;

Input : A set $T$

Output : The set of the $|T|-1$ edges of $(T,\succ)$

3 Let $T=\\{t_{1},\dots,t_{n}\\}$

4 $H\leftarrow T$

5 $\mathcal{C}\leftarrow\\{\\}$ // The chain decomposition

6 while  _$H\neq\emptyset$_ do

7 Let $H=\\{h_{1},h_{2},\dots,h_{m}\\}$

8 $x\leftarrow h_{1}$

9 for  _$i=2,\ldots,m$_ do

10 if  _$x\succ h_{i}$_ then

11 $x\leftarrow h_{i}$

12 end if

13

14 end for

15 $c\leftarrow[]$ //An empty list

16 for  _$i=1,\ldots,m$_ do

17 if  _$x=h_{i}$ or $h_{i}\succ x$_ then

18 Append $h_{i}$ to $c$

19 $H\leftarrow H\setminus\\{h_{i}\\}$

20 end if

21

22 end for

23 Sort $c$ according to the relation $\succ$

24 $\mathcal{C}\leftarrow\mathcal{C}\cup\\{c\\}$

25

26 end while

27Let $\mathcal{C}=\\{c_{1},\dots,c_{w}$}

28 $E\leftarrow\\{\\}$ //The set of edges

29 for  _$i=1,\ldots,w$_ do

30 Let $c_{i}=\\{d_{1},\dots,d_{|c_{i}|}\\}$

31 Let $t_{n+1}\succ t_{i}$ for all $i\in\\{1,\dots,n\\}$

32 $x\leftarrow t_{n+1}$

33 for  _$i=1,\ldots,n$_ do

34 if  _$t_{i}\succ d_{1}$ and $x\succ t_{i}$_ then

35 $x\leftarrow t_{i}$

36 end if

37

38 end for

39 if  _$x\neq t_{n+1}$_ then

40 $E\leftarrow E\cup\\{(x,d_{1})\\}$

41 end if

42

43 for  _$i=1,\dots,|c_{i}|-1$_ do

44 $E\leftarrow E\cup\\{(d_{i},d_{i+1})\\}$

45 end for

46

47 end for

return _E_