Recognizing Union-Find trees is NP-complete✩
Kitti Gelle1 , Szabolcs Iván1
a University

of Szeged, Hungary

arXiv:1510.07462v2 [cs.CC] 5 Jan 2017

Abstract
Disjoint-Set forests, consisting of Union-Find trees are data structures having a widespread practical application due to their efficiency. Despite them being well-known, no exact structural characterization of these
trees is known (such a characterization exists for Union trees which are constructed without using path
compression). In this paper we provide such a characterization by means of a simple push operation and
show that the decision problem whether a given tree is a Union-Find tree is NP-complete.
1. Introduction
Disjoint-Set forests, introduced in [10], are fundamental data structures in many practical algorithms where one has to maintain a partition of
some set, which support three operations: creating a partition consisting of singletons, querying
whether two given elements are in the same class of
the partition (or equivalently: finding a representative of a class, given an element of it) and merging
two classes. Practical examples include e.g. building a minimum-cost spanning tree of a weighted
graph [4], unification algorithms [17] etc.
To support these operations, even a linked list
representation suffices but to achieve an almostconstant amortized time cost per operation,
Disjoint-Set forests are used in practice. In this
data structure, sets are represented as directed
trees with the edges directed towards the root; the
create operation creates n trees having one node
each (here n stands for the number of the elements in the universe), the find operation takes
a node and returns the root of the tree in which the
node is present (thus the same-class(x, y) operation is implemented as find(x) == find(y)), and
the merge(x, y) operation is implemented by merging the trees containing x and y, i.e. making one of
the root nodes to be a child of the other root node
(if the two nodes are in different classes).
In order to achieve near-constant efficiency, one has
to keep the (average) height of the trees small.
✩ This research was supported by NKFI grant number
K108448.

Preprint submitted to Elsevier

There are two “orthogonal” methods to do that:
first, during the merge operation it is advisable to
attach the “smaller” tree below the “larger” one. If
the “size” of a tree is the number of its nodes, we
say the trees are built up according to the union-bysize strategy, if it’s the depth of a tree, then we talk
about the union-by-rank strategy. Second, during
a find operation invoked on some node x of a tree,
one can apply the path compression method, which
reattaches each ancestor of x directly to the root
of the tree in which they are present. If one applies both the path compression method and either
one of the union-by-size or union-by-rank strategies,
then any sequence of m operations on a universe
of n elements has worst-case time cost O(mα(n))
where α is the inverse of the extremely fast growing (not primitive recursive) Ackermann function
for which α(n) ≤ 5 for each practical value of
n (say, below 265535 ), hence it has an amortized
almost-constant time cost [22]. Since it’s proven [9]
that any data structure has worst-case time cost
Ω(mα(n)), the Disjoint-Set forests equipped with
a strategy and path compression offer a theoretically optimal data structure which performs exceptionally well also in practice. For more details see
standard textbooks on data structures, e.g. [4].
Due to these facts, it is certainly interesting both
from the theoretical as well as the practical point of
view to characterize those trees that can arise from
a forest of singletons after a number of merge and
find operations, which we call Union-Find trees in
this paper. One could e.g. test Disjoint-Set implementations since if at any given point of execution
January 6, 2017

a tree of a Disjoint-Set forest is not a valid UnionFind tree, then it is certain that there is a bug in
the implementation of the data structure (though
we note at this point that this data structure is
sometimes regarded as one of the “primitive” data
structures, in the sense that is is possible to implement a correct version of them that needs not be
certifying [20]). Nevertheless, only the characterization of Union trees is known up till now [2], i.e.
which correspond to the case when one uses one of
the union-by- strategies but not path compression.
Since in that case the data structure offers only a
theoretic bound of Θ(log n) on the amortized time
cost, in practice all implementations imbue path
compression as well, so for a characterization to be
really useful, it has to cover this case as well.
In this paper we show that the recognition problem of Union-Find trees is NP-complete when the
union-by-size strategy is used (and leave open the
case of the union-by-rank strategy). This confirms
the statement from [2] that the problem “seems
to be much harder” than recognizing Union trees
(which in turn can be done in low-degree polynomial time).
Related work. There is an increasing interest in determining the complexity of the recognition problem of various data structures. The
problem was considered for suffix trees [16, 21],
(parametrized) border arrays [14, 19, 8, 13, 15], suffix arrays [1, 7, 18], KMP tables [6, 12], prefix tables [3], cover arrays [5], and directed acyclic wordand subsequence graphs [1].

the subtree (Vx = {y ∈ Vt : x t y}, x, parentt |Vx )
of t rooted at x. When x, y ∈ Vt , we say that x
is lighter than y in t (or y is heavier than x) if
size(t, x) < size(t, y).
Two operations on trees are that of merging and collapsing.
Given two trees
t
=
(Vt , roott , parentt ) and s
=
(Vs , roots , parents ) with Vt and Vs being disjoint, their merge merge(t, s) (in this
order) is the tree (Vt ∪ Vs , roott , parent)
with parent(x) = parentt (x) for x ∈ Vt ,
parent(roots ) = roott and parent(y) =
parents (y) for each non-root node y ∈ Vs of
s. Given a tree t = (V, root, parent) and a
node x ∈ V , then collapse(t, x) is the tree
(V, root, parent′ ) with parent′ (y) = root
if y is a non-root ancestor of x in t, and
parent′ (y) = parent(y) otherwise. For examples, see Figure 1.
The class of Union trees is the least class of trees
satisfying the following two conditions: every singleton tree (having exactly one node) is a Union
tree, and if t and s are Union trees with size(t) ≥
size(s), then merge(t, s) is a Union tree as well.
Analogously, the class of Union-Find trees is the
least class of trees satisfying the following three conditions: every singleton tree is a Union-Find tree, if
t and s are Union-Find trees with size(t) ≥ size(s),
then merge(t, s) is a Union-Find tree as well, and
if t is a Union-Find tree and x ∈ Vt is a node of t,
then collapse(t, x) is also a Union-Find tree.
We’ll frequently sum the size of “small enough” children of nodes, so we introduce a shorthand also for
that: for a tree t, a node x of t, andPa threshold W ≥
0, let sumsize(t, x, W ) stand for {size(t, y) : y ∈
children(t, x), size(t, y) ≤ W }. We say that a
node x of a tree t satisfies the Union condition if
for each child y of x we have sumsize(t, x, W ) ≥ W
where W = size(t, y) − 1. Otherwise, we say that
x violates the Union condition (at child y). Then,
the characterization of Union trees from [2] can be
formulated in our terms as follows:

2. Notation
A tree is a tuple t = (Vt , roott , parentt ) with Vt
being the finite set of its nodes, roott ∈ Vt its
root and parentt : (Vt − {roott }) → Vt mapping
each non-root node to its parent (so that the graph
of parentt is a directed acyclic graph, with edges
being directed towards the root).
For a tree t and a node x ∈ Vt , let children(t, x)
stand for the set {y ∈ Vt : parentt (y) = x} of its
children and children(t) stand as a shorthand for
children(t, roott ), the set of depth-one nodes of
t. Two nodes are siblings in t if they have the same
parent. Also, let x t y denote that x is an ancestor
of y in t, i.e. x = parentkt (y) for some k ≥ 0
and let size(t, x) = |{y ∈ Vt : x t y}| stand for
the number of descendants of x (including x itself).
Let size(t) stand for size(t, roott ), the number of
nodes in the tree t. For x ∈ Vt , let t|x stand for

Theorem 1. A tree t is a Union tree if and only
if each node x of t satisfies the Union condition.
Equivalently, x satisisfies the Union condition if and
only if whenever x1 , . . . , xk is an enumeration of
children(t, x) such
P that size(t, xi ) ≤ size(t, xi+1 )
for each i, then j<i size(t, xj ) ≥ size(t, xi ) − 1
for each i = 1, . . . , k. (In particular, each non-leaf
node has to have a leaf child.)
2

3. Structural characterization of Union-Find
trees

nodes, x has to have depth at least two in s as
well. Let {x1 , . . . , xk } stand for X − Y . Now for
any node xi ∈ X − Y there exists a unique node
yi ∈ Y such that yi s xi . Let us define the
trees t0 = t, ti = push(ti−1 , xi , yi ). Then t ⊢∗ tk ,
children(tk ) = Y = children(s) and for each
y ∈ Y , tk |y  s|y . Applying the induction hypothesis we get that tk |y ⊢∗ s|y for each y ∈ Y , hence the
immediate subtrees of tk can be transformed into
the immediate subtrees of s by repeatedly applying
push operations, hence t ⊢∗ s as well.

Suppose t and s are trees on the same set V of nodes
and with the same root r. We write t  s if x t y
implies x s y for each x, y ∈ V . For an example,
consult Figure 1. There, t′′′  t′′ (e.g. r t′′′ x and
also r t′′ x); the reverse direction does not hold
since e.g. y t′′ z but y 6t′′′ z. Also, the reader is
encouraged to verify that t′′′  t′  t′′ also holds.
Clearly,  is a partial order on any set of trees
(i.e. is a reflexive, transitive and antisymmetric relation). It is also clear that t  s if and only if
parentt (x) s x holds for each x ∈ V − {r} which
is further equivalent to requiring parentt (x) s
parents (x) since parentt (x) cannot be x.
Another notion we define is the (partial) operation
push on trees as follows: when t is a tree and
x 6= y ∈ Vt are siblings in t, then push(t, x, y)
′
is defined as the
( tree (Vt , roott , parent ) with
y
if z = x,
parent′ (z) =
, that is,
parentt (z) otherwise
we “push” the node x one level deeper in the tree
just below its former sibling y. (See Figure 1.)
We write t ⊢ t′ when t′ = push(t, x, y) for
some x and y, and as usual, ⊢∗ denotes the
reflexive-transitive closure of ⊢. Observe that when
t′ = push(t, x, y), then size(t′ , y) = size(t, y) +
size(t, x) > size(t, y) and size(t′ , z) = size(t, z)
for each z 6= y, hence ⊢∗ is also a partial ordering
on trees. This is not a mere coincidence:

The relations  and ⊢∗ are introduced due to their
intimate relation to Union-Find and Union trees:
Theorem 2. A tree t is a Union-Find tree if and
only if t ⊢∗ s for some Union tree s.
Proof. Let t be a Union-Find tree. We show the
claim by structural induction. For singleton trees
the claim holds since any singleton tree is a Union
tree as well. Suppose t = merge(t1 , t2 ). Then by
the induction hypothesis, t1 ⊢∗ s1 and t2 ⊢∗ s2
for the Union trees s1 and s2 . Then, for the tree
s = merge(s1 , s2 ) we get that t ⊢∗ s. Finally,
assume t = collapse(t′ , x) for some node x. Let
x = x1 ≻ x2 ≻ . . . ≻ xk = roott′ be the ancestral
sequence of x in t′ . Then, defining t0 = t, ti =
push(ti−1 , xi , xi+1 ) we get that t ⊢∗ tk−1 = t′ and
t′ ⊢∗ s for some Union tree applying the induction
hypothesis, thus t ⊢∗ s also holds.
Now assume t ⊢∗ s (equivalently, t  s by Proposition 1) for some Union tree s. Let X stand
for the set children(t) of depth-one nodes of t
and Y stand for children(s). By t  s we get
that Y ⊆ X. Let {x1 , . . . , xk } stand for the set
X − Y . Then for each xi there exists a unique
yi ∈ Y with yi s xi . Let us define the sequence
t = t0 ⊢ t1 ⊢ . . . ⊢ tk with ti = push(ti−1 , xi , yi ).
Then, tk  s holds. Moreover, as children(tk ) =
children(s) = Y , we get that tk |y  s|y for each
y ∈ Y . Applying the induction hypothesis we have
that each subtree tk |y is a Union-Find tree. Now
let us define the sequence t′0 , t′1 , . . . , t′k of trees as
follows: t′0 is the singleton tree with root roott ,
and t′i = merge(t′i−1 , tk |yi′ ) where Y = {y1′ , . . . , yℓ′ }
is an enumeration
of Y such that
Pof the members
size(s, yi′ ) ≤ 1 +
size(s, yj′ ) for each i = 1, . . . , ℓ.

Proposition 1. For any pair s and t of trees, t  s
if and only if t ⊢∗ s.
Proof. For ⊢∗ implying  it suffices to show that
⊢ implies  since the latter is a partial order. So
let t = (V, r, parent), and x 6= y ∈ V be siblings in
t with the common parent z, and s = push(t, x, y).
Then, since parentt (x) = z = parents (y) =
parents (parents (x)), we get parentt (x) s x,
and by parentt (w) = parents (w) for each node
w 6= x, we have t  s.
It is clear that  is equality on singleton trees, thus
 implies ⊢∗ for trees of size 1. We apply induction
on the size of t = (V, r, parent) to show that whenever t  s = (V, r, parent′ ), then t ⊢∗ s as well.
Let X stand for the set children(t) of depth-one
nodes of t and Y stand for children(s). Clearly,
Y ⊆ X since by t  s, any node x of t having
depth at least two has to satisfy parent(x) s
parent′ (x) and since parent(x) 6= r for such

j<i

(Such an orderingP
exists as s is a Union tree.) Since
size(s, yj′ ), we get thet each t′i
size(t′i−1 ) = 1 +
j<i

is a Union-Find tree as well.
3

Finally, the tree t results from the tree t′k
constructed above by applying successively one
collapse operation on each node in X − Y , hence
t is a Union-Find tree as well.

an ancestor of y in t′ (alliwing y = z), thus by
size(t′ , z) ≥ size(t′ , y) ≥ size(t, y) we get that z is
heavy in t′ hence x is a basket of t′ as well.
We will frequently sum the sizes of the light children of nodes, so for a tree t and node x of t, let
sumlight(t, x) stand for sumsize(t, x, H), the total size of the light children of x in t.
We introduce a charge function c as follows: for a
tree t and node x ∈ Vt , let the charge of x in t,
denoted c(t, x), be
(
0
if x is a light node of t,
c(t, x) =
sumlight(t, x) − H otherwise.

4. Complexity
In this section we show that the recognition of
Union-Find trees is NP-complete. Note that membership in NP is clear by Theorem 2 and that the
possible number of pushes is bounded above by n2 :
upon pushing x below y, the size of y increases,
while the size of the other nodes remains the same.
Since the size of any node is at most n, the sum of
the sizes of all the nodes is at most n2 in any tree.
Let H > 0 be a parameter (which we call the “heaviness threshold parameter” later on) to be specified later and t = (V, root, parent) be a tree.
We call a node x light if size(t, x) ≤ H, heavy if
size(t, x) > H, and a basket if it has a heavy child
in t. Note that every basket is heavy. A particular
type of basket is an empty basket which is a node
having a single child of size H + 1. (Thus empty
baskets have size H + 2.)
Let us call a tree t0 flat if it satisfies all the following
conditions:

It’s worth observing that when x is a non-basket
heavy node of t, then sumlight(t, x) = size(t, x)−
1 (since by being non-basket, each child of x is
light).
Note that in particular the charge of a node is computable from the multiset of the sizes of its children
(or, from the multiset of the sizes of its light children along with its own size). Let t′ = push(t, x, y)
and let z = parentt (y) be the common parent
of x and y in t. Then, c(t, w) = c(t′ , w) for each
node w ∈
/ {y, z} since for those nodes this multiset does not change. We now list how c(t′ , y) and
c(t′ , z) vary depending on whether y and x are light
or heavy nodes. Note that size(t′ , z) = size(t, z)
(thus the charge of z can differ in t and t′ only if
z is heavy and sumlight(t′ , z) 6= sumlight(t, z))
and size(t′ , y) = size(t, x) + size(t, y).

1. There are K > 0 depth-one nodes of t0 which
are empty baskets.
2. There is exactly one non-basket heavy depthone node of t0 , with size H + 1.
3. The total size of light depth-one nodes is (K +
1)·H. That is, sumsize(t0 , roott0 , H) = (K +
1) · H.
4. The light nodes and non-basket heavy nodes
have only direct children as descendants, thus
in particular, the subtrees rooted at these
nodes are Union trees.

i) If x and y are both light nodes with size(t, x)+
size(t, y) ≤ H (i.e. y remains light in t′ after
x is pushed below y) then sumlight(t′ , z) =
sumlight(t, z) hence c(t, z) = c(t′ , z) and
c(t′ , y) = c(t, y) = 0 since y is still light in
t′ .
ii) If x and y are both light nodes with size(t, x)+
size(t, y) > H (i.e. y becomes heavy due to
the pushing), then z is heavy as well (both in
t and in t′ since size(t, z) = size(t′ , z)). Then
since sumlight(t′ , z) = sumlight(t, z) −
(size(t, x) + size(t, y)), we get c(t′ , z) =
c(t, z) − (size(t, x) + size(t, y)) and c(t′ , y) =
size(t, y) + size(t, x) − (H + 1) since y is heavy
in t′ having only light children (by the assumption, x is still light and each child of y already
present in t have to be also light since y itself
is light in t).
iii) If x is heavy and y is in light in t, then after pushing, y becomes heavy as well (and z

See Figure 2.
The fact that the push operation cannot decrease
the size of a node has a useful corollary:
Proposition 2. If t ⊢∗ t′ , and x is a heavy (basket,
resp.) node of t, then x is a heavy (basket, resp.)
node of t′ as well. Consequently, if x is light in t′ ,
then x is light in t as well.
Proof. Retaining heaviness simply comes from
size(t, x) ≤ size(t′ , x). When x is a basket node
of t, say having a heavy child y, then by x t y
and t ⊢∗ t′ (that is, t  t′ ) we get x t′ y
as well, hence x has a (unique) child z which is
4

is also heavy). Then, by sumlight(t′ , z) =
sumlight(t, z) − size(t, y) (since the child y
of z loses its status of being light) we have
c(t′ , z) = c(t, z) − size(t, y) and in t′ , y is a
heavy node with light children of total size
size(t, y) − 1, hence c(t′ , y) = size(t, y) − (H +
1) (while c(t, y) = 0 since y is light in t).
iv) If x is light and y is heavy in t, then z is heavy
as well, z loses its light child x while y gains the
very same light child, hence c(t′ , z) = c(t, z) −
size(t, x) and c(t′ , y) = c(t, y) + size(t, x).
v) Finally, if both x and y are heavy, then z is
heavy as well, and since neither z nor y loses
or gains a light child, c(t′ , z) = c(t, z) and
c(t′ , y) = c(t, y).

thus sumlight(t, x) ≥ H yielding c(t, x) =
sumlight(t, x) − H ≥ 0 and the statement is
proved.
Thus, since a flat tree has total charge 0 while in a
Union tree each node has nonnegative charge, and
the push operation either decreases the total charge
in Cases ii) and iii) above, or leaves the total charge
unchanged in the other cases, we get the following:
Lemma 1. Suppose t0 ⊢∗ t for a flat tree t0 and a
Union tree t. Then for any sequence of push operations transforming t0 into t, each push operation is
of type i), iv) or v) above, i.e.
• either a light node is pushed into a light node,
yielding still a light node;

Observe
that P
in Cases i), iv) and v) we have
P
c(t′ , x) while in Cases ii) and iii)
c(t, x) =
x∈V
x∈Vt
P
Pt
c(t′ , x) (namely, the
c(t, x) >
it holds that
x∈Vt

• or some node (either heavy or light) is pushed
into a heavy node.

x∈Vt

total charge decreases by H + 1 in these two cases).
Now for a P
flat tree t0 it is easy to
c(t0 , x) is zero:
we have
check that

Moreover, the charge of each node of t has to be
zero.
In particular, a heavy node x has charge 0 in a tree
t if and only if sumlight(t, x) = H yielding also
that each non-basket heavy node of t has to be of
size exactly H + 1. It’s also worth observing that
by applying the above three operations one does
not create a new heavy node: light nodes remain
light all the time. Moreover, if for a basket node
sumlight(t, x) = H in a Union tree t, then there
has to exist a heavy child of x in t of size exactly
H + 1 (by x being a basket node, there exists a
heavy child and if the size of the lightest heavy child
is more than H + 1, then the Union condition gets
violated).
Recall that in a flat tree t0 with K empty baskets,
there are K + 1 baskets in total (the depth-one
empty baskets and the root node), and there are
K + 1 non-basket heavy nodes (one in each basket,
initially), each having size H + 1, and all the other
nodes are light.
Thus if t0 ⊢∗ t for some Union tree t, then the set
of non-basket heavy nodes coincide in t0 and in t,
and also in t, the size of each such node x is still
H + 1. In particular, one cannot increase the size
of x by pushing anything into x.
Summing up the result of the above reasoning we
have:

x∈Vt0

sumlight(t0 , roott0 ) = (K + 1) · H by assumption, hence the root node is in particular
heavy and c(t0 , roott0 ) = K · H, the empty
baskets (having no light node at all) have charge
−H each and there are K of them, finally, all the
heavy nodes of size H + 1 have charge zero as well
as each light node, making up the total sum of
charges to be zero.
The charge function we introduced turns out to be
particularly useful due to the following fact:
Proposition 3. If t is a Union tree, then c(t, x) ≥
0 for each node of t.
Proof. If x is a light node of t, then c(t, x) = 0
and we are done.
If x is a heavy node which is not a basket, then all of
its children are light nodes, thus sumlight(t, x) =
size(t, x) − 1, making c(t, x) = size(t, x) − (H +
1) which is nonnegative since size(t, x) > H by x
being heavy.
Finally, if x is a basket node of t, then it has at
least one heavy child. Let y be a lightest heavy
child of x. Since t is a Union tree, we have
sumsize(t, x, size(t, y) − 1) ≥ size(t, y) − 1. By
the choice of y, every child of x which is lighter
than y is light itself, thus sumsize(t, x, size(t, y) −
1) = sumsize(t, x, H) = sumlight(t, x), moreover, size(t, y) − 1 ≥ H since y is heavy,

Lemma 2. Suppose t0 ⊢∗ t for some flat tree t0
and some Union tree t. Then for any pushing sequence transforming t0 into t, each step ti ⊢ ti+1 of
5

basket) and each child of x also has the same
size in t′ as in t, hence the Union condition is
still violated. Now assume z and w are children of x. Upon pushing, x loses a child of size
size(t, z) and a child of size size(t, w) and gains a
child of size size(t, z) + size(t, w). It is clear that
sumsize(t, x, W ) ≥ sumsize(t′ , x, W ) for each possible W then (equality holds when W ≥ size(t, z)+
size(t, w) or W < min{size(t, w), size(t, z)} and
strict inequality holds in all the other cases). It
is also clear that there is at least one child y ′
of x in t′ such that size(t, y) ≤ size(t′ , y ′ ): if
y 6= z then y ′ = y suffices, otherwise y ′ = w
is fine. Now let y0 be such a child with W =
size(t′ , y0 ) being the minimum possible. Then
sumsize(t′ , x, W − 1) = sumsize(t′ , x, size(t, y) −
1) ≤ sumsize(t, x, size(t, y) − 1) < size(t, y) − 1 ≤
size(t′ , y0 ) − 1 and thus x still violates the Union
condition in t′ as well.

the push chain with ti+1 = push(ti , x, y) has to be
one of the following two forms:
• x and y are light in ti and in ti+1 as well.
• y is a basket in ti (and in ti+1 as well).
We can even restrict the order in which the above
operations are applied.
Lemma 3. If t0 ⊢∗ t for some flat tree t0 and
Union tree t, then there is a push sequence t0 ⊢
t1 ⊢ . . . ⊢ tk = t with ti+1 = push(ti , xi , yi ) and an
index ℓ such that for each i ≤ ℓ, yi is a basket node
and for each i > ℓ, both xi and yi are light nodes
with size(ti , xi ) + size(ti , yi ) ≤ H.
Proof. Indeed, assume ti+1 = push(ti , x, y) for
the light nodes x and y of ti with size(ti , x) +
size(ti , y) ≤ H and ti+2 = push(ti+1 , z, w) for the
basket w of ti+1 . Then we can modify the sequence
as follows:

Hence we have:

• if z = y, then we can get ti+2 from ti by pushing x and y into the basket w first, then pushing x into y;

Proposition 5. Suppose t0 is a flat tree. Then, t0
is a Union-Find tree if and only if t0 ⊢ t1 ⊢ . . . ⊢
tk for some Union tree tk such that at each step
ti ⊢ ti+1 of the chain with ti+1 = push(ti , x, y), the
node y is a basket node in ti (and consequently, in
all the other members of the sequence as well).

• otherwise we can simply swap the two push operations since w cannot be either x or y (since
light nodes are not baskets), nor descendants
of x or y, thus z and w are already siblings in
ti as well, hence z can be pushed into w also
in ti , and afterwards since x and y are siblings
in the resulting tree, x can be pushed into y.

Proof. Observe that initially in any flat tree t0 ,
only basket nodes violate the Union condition.
Moreover, by pushing arbitrary nodes into baskets
only the baskets’ Union status can change (namely,
upon pushing into some basket x, the status of x
and its parent can change, which is also a basket).
Thus, after pushing nodes into baskets we either already have a Union tree, or not, but in the latter
case we cannot transform the tree into a Union tree
by pushing light nodes into light nodes by Proposition 4.

Applying the above modification finitely many
times we arrive to a sequence of trees satisfying the
conditions of the Lemma. Thus if t0 ⊢∗ t for some
flat tree t0 and Union tree t, we can assume that
first we push nodes into baskets, then light nodes
into light nodes, yielding light nodes.
However, it turns out the latter type of pushing
cannot fix the Union status of the trees we consider.

Hence we arrive to the following characterization:

Proposition 4. Suppose t is a tree with a basket
node x violating the Union condition, i.e. for some
child y of x it holds that sumsize(t, x, size(t, y) −
1) < size(t, y) − 1. Then for any tree t′ =
push(t, z, w) with z and w being light nodes with
total size at most H we have that x still violates
the Union condition in t′ .

Proposition 6. Assume t0 is a flat tree having K
empty baskets. Then, t0 is a Union-Find tree if and
only if the set L of its depth-one light nodes can
be partitioned into sets
P L1 , . . . , LK+1 such that for
each 1 ≤ i ≤ KP+ 1, x∈Li size(t0 , x) = H and for
each y ∈ Li ,
z∈Li ,size(t0 ,z)<size(t0 ,y) size(t0 , z) ≥
size(t0 , y) − 1.

Proof. If z (and w) are not children of x, then
children(t, x) = children(t′ , x) (since in particular w 6= x by w being light and x being a

Proof. Recall that non-basket nodes of a flat tree
satisfy the Union condition. Assume the set L
6

offset c ≥ 0, the instance I ′ = a′1 , . . . , a′3m with
a′i = ai + c for each i and with B ′ = B + 3c, the
set of solutions of I and I ′ coincide. Indeed, the
instance I ′ still satisfies

of the depth-one light nodes of t0 can be partitioned into sets Li , i = 1, . . . , K + 1 as above. Let
y1 , . . . , yK be the empty basket nodes of t0 . Then
by pushing every member of Li into the basket yi
(and leaving members of LK+1 at depth one) we
arrive to a tree t whose basket nodes satisfy the
Union condition (their light children do not violate
the condition due to the assumption on Li , and
their only heavy child having size H + 1 does not
violate
the condition either since sumlight(t, x) =
P
x∈Li size(t0 , x) = H due also to the assumption
on Li . Finally, the root node has K children (the
initially empty baskets) of size 2H + 2 but since it
has light children of total size H and a heavy child
of size H + 1, their sizes summing up to 2H + 1,
the depth-one baskets also do not violate the Union
condition. Hence t0 ⊢∗ t for some Union tree t, thus
is a Union-Find tree.
For the other direction, assume t0 is a Union-Find
tree. Then since t0 is also a flat tree, it can be transformed into a Union tree t by repeatedly pushing
nodes into baskets only. Since the pushed nodes’
original parents are baskets as well (since they are
parents of the basket into which we push), a node
is a child of a basket node in t if and only if it is
a child of a (possibly other) basket node in t0 . We
also know that the charge of each node in the Union
tree we gain at the end has to be zero, in particular, each basket x still has to have a heavy child of
size exactly H + 1 and sumlight(t, x) = H has to
hold. Let y1 , . . . , yK+1 stand for the basket nodes
of t0 (and of t as well): then, defining Li as the set
of light children of yi in t suffices.

B′
4

=
=

B + 3c
B
3
B
=
+ c<
+ c < ai + c = a′i
4
4
4
4
3
B + 3c
B′
B
+ c=
=
,
ai + c <
2
2
2
2

′
hence each solution B ′P= {B1′ , . . . , Bk′ } of
PI still
′
contains triplets and
i∈Bj′ ai
i∈Bj′ ai = 3c +
P
′
which is B if and only if i∈B ′ ai = B, thus any
j
solution of I ′ is also a solution of I, the other direction being also straightforward to check.
Thus, by setting the above offset to c = ⌈(1 +
max{2⌈log B⌉ , 24 }−B)/3⌉ (in which case B ′ = 2D +d
for some suitable integers D > 3 and d ∈ {1, 2, 3})
we get that the following problem is also strongly
NP-complete:

Definition 1 (3-Partition’). Input: A sequence
aP1 , . . . , a3m of positive integers such that B =
3m
i=1 ai
is a positive integer of the form 2D + d
m
for some integer D > 3 and d ∈ {1, 2, 3} and
B
B
4 < ai < 2 for each i = 1, . . . , 3m.
Output: Does there exist a partition B =
{B
P 1 , . . . , Bk } of the set {1, . . . , 3m} satisfying
i∈Bj ai = B for each j ∈ {1, . . . , k}?
Observe that in any solution, k = m and each Bj
consists of exactly three elements.
We are now ready to show the NP-completeness of
the recognition of Union-Find trees via a (logspace,
many-to-one) reduction from the 3-Partition’
problem to it. To each instance I = a1 , . . . , a3m
of the 3-Partition’ problem we associate the following flat tree t(I):

At this point we recall that the following problem 3Partition is NP-complete in the strong sense [11]:
given a list aP1 , . . . , a3m of positive integers with the
3m
ai
being an integer, such that for
value B = i=1
m
each 1 ≤ i ≤ 3m we have B4 < ai < B2 , does
there exist a partition B P
= {B1 , . . . , Bk } of the
set {1, . . . , 3m} satisfying i∈Bj ai = B for each
1 ≤ j ≤ k?
(Here “in the strong sense” means that the problem remains NP-complete even if the numbers are
encoded in unary.)
Observe that by the condition B4 < ai < B2 each set
Bj has to contain exactly three elements (the sum
of any two of the input numbers is less than B and
the sum of any four of them is larger than B), thus
in particular in any solution above k = m holds.
Note also that for any given instance I =
a1 , . . . , a3m of the above problem and any given

• The number K of empty baskets in t(I) is m −
1.
• The heaviness threshold parameter H of the
tree is B + P
2D−1 − 1 where B = 2D + d is the
3m
ai
with D > 3 being an integer
target sum i=1
m
and d ∈ {1, 2, 3}.
• There are 3m + (D − 1)m light nodes of depth
one in t(I): first, to each member ai of the
input a light node xi of size ai is associated,
and to each index 1 ≤ i ≤ m and 0 ≤ j < D−1,
a light node yij of size wij = 2j is associated.
7

2D−2 ≥ 2 if D ≥ 3). Thus by Proposition 6, t(I) is
indeed a Union-Find tree. (See Figure 4.)
For the other direction, suppose t(I) is a UnionFind tree. Then by Proposition 6, the multiset of
the sizes of the light nodes can be partitioned into
sets L = {L1 , . . . , Lm } such that each Li sums up
exactly to H = B + 2D−1 − 1 and each Li satisfies
the Union condition.
First we show that each Li contains exactly one
“small” weight wkj for each j = 0, . . . , D − 2. (Note
that each aj exceeds 2D−2 hence the name of these
weights.) We prove this by induction on j. The
claim holds for j = 0 since in a Union-Find tree
each inner node has a leaf child. By induction, the
smallest j members of Li have sizes 20 , 21 , . . . , 2j−1 ,
summing up to 2j − 1. Since all the weights ak
′
are larger than 2D−2 as well as the weights wkj for
j ′ > j, none of these can be the (j + 1)th smallest
integer in Li without violating the Union condition.
Thus, each set Li has to have some wkj i as its j +
1th smallest element, and since both the number
of these sets and the number of the small weights
of size 2j are m we get that each set Li contains
exactly one small weight of size 2j .
Thus, the small weights sum up exactly to 2D−1 − 1
in each of the sets Li , hence the weights ai have to
sum up exactly to H − (2D−1 − 1) = 2D + d =
B in each of these sets, yielding a solution to the
instance (a1 , . . . , a3m ) of the 3-Partition’ problem
and concluding the proof.

Note that since the 3-Partition’ problem is
strongly NP-complete we can assume that the input numbers ai are encoded in unary, thus the tree
t(I) can be indeed built in logspace (and in polytime).
(See Figure 3 for an example.)
In order to ease notation we say that a member ai
of some sequence (or multiset) a1 , . . . , an satisfies
the Union condition if the sum of the members of
the sequence
that are less than ai is at least ai − 1,
P
i.e.
aj ≥ ai − 1. In addition we say that the
aj <ai

sequence itself satisfies the Union condition if each
of its elements does so. It is clear that a node x of
a tree t satisfies the Union condition if and only if
the multiset {size(t, y) : y ∈ children(t, x)} does
so.
The following lemma states that the above construction is indeed a reduction:

Lemma 4. For any instance I of the 3Partition’ problem, I has a solution iff t(I)
is a Union-Find tree.
Proof. For one direction, assume {B1 , . . . , Bm } is
a solution of the instance I = a1 , . . . , a3m . Then
the multiset of the sizes of the light nodes can be
partitioned into sets L = (L1 , . . . , Lm ) as Li = {aj :
j ∈ Bi } ∪ {wij : 0 ≤ j < D − 1}. It is clear that
P
D−1
− 1 = H. Thus, by Propoℓ∈Li ℓ = B + 2
sition 6 we only have to show that each Li satisfies the Union condition. For the elements wij of
′
Pj−1
size 2j it is clear since j ′ =0 wij = 2j − 1. Now
let a be the smallest element of Bi . Then, since
Bi consists of three integers summing up to B, we
get that a ≤ B3 . On the other hand, B4 < a by
the definition of the 3-Partition’ problem. Recall
that B = 2D + d for some d ∈ {1, 2, 3}: we get
that 2D−2 < a, thus in particular each weight wij
is smaller
than a. Summing up all these weights
PD−2
j
D−1
− 1. We claim that
we get
j=0 wi = 2
B
3

2D +d
3
D

Thus, since the strongly NP-complete 3Partition’ problem reduces to the problem
of deciding whether a flat tree is a Union-Find
tree, and moreover, if a flat tree is a Union-Find
tree, then it can be constructed from a Union tree
by applying finitely many path compressions (all
one has to do is to “move out” the light nodes from
the baskets by calling a find operation on each of
them successively), we have proven the following:
Theorem 3. It is NP-complete already for flat
trees to decide whether

D−1

=
< 2
− 1. Indeed, multiplying
a ≤
by 3 we get 2 + d < 2D + 2D−1 − 3, subtracting 2D and adding 3 yields d + 3 < 2D−1 which
holds since d ≤ 3 and D > 3. Thus we have that
a satisfies the Union condition as well. Then, if
b > a is P
also a member of Bi , then it suffices to
D−2
show a + j=0 wij ≥ b − 1 but since a ≥ B4 > 2D−2
PD−2 j
and j=0 wi = 2D−1 − 1, we get the left sum exceeds 2D−1 + 2D−2 − 1 which is at least b − 1 since
D
b < B2 = 2 2+d ≤ 2D−1 + 2D−2 (since d ≤ 3 and

i) a given (flat) tree is a Union-Find tree and
ii) whether a given (flat) tree can be constructed
from a Union tree by applying a number of path
compression operations.
5. Conclusion, future directions
We have shown that unless P = NP, there is no
efficient algorithm to check whether a given tree
8

is a valid Union-Find tree, assuming union-by-size
strategy and usage of path compression, since the
problem is NP-complete. A natural question is
whether the recognition problem remains NP-hard
assuming union-by-rank strategy (and of course
path compression)? Since the heights of merged
trees do not add up, only increase by at most one,
there is no “obvious” way to encode arithmetic into
the construction of these trees, and even the characterization by the push operation is unclear to hold
in that case (since in that setting, path compression
can alter the order of the subsequent merging).

[12]

[13]

[14]

[15]

References
[16]

[1] H. Bannai, S. Inenaga, A. Shinohara, and M. Takeda.
Inferring strings from graphs and arrays. Lecture
Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics), 2747:208–217, 2003. cited By 15.
[2] Leizhen Cai. The recognition of union trees. Inf. Process. Lett., 45(6):279–283, 1993.
[3] Julien Clément, Maxime Crochemore, and Giuseppina
Rindone. Reverse engineering preﬁx tables. In Susanne
Albers and Jean-Yves Marion, editors, 26th International Symposium on Theoretical Aspects of Computer
Science, STACS 2009, February 26-28, 2009, Freiburg,
Germany, Proceedings, volume 3 of LIPIcs, pages 289–
300. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009.
[4] Thomas H. Cormen, Cliﬀord Stein, Ronald L. Rivest,
and Charles E. Leiserson. Introduction to Algorithms.
McGraw-Hill Higher Education, 2nd edition, 2001.
[5] M. Crochemore, C.S. Iliopoulos, S.P. Pissis, and G. Tischler. Cover array string reconstruction. Lecture
Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics), 6129 LNCS:251–259, 2010. cited
By 8.
[6] J.-P. Duval, T. Lecroq, and A. Lefebvre. Eﬃcient validation and construction of border arrays and validation
of string matching automata. RAIRO - Theoretical Informatics and Applications, 43(2):281–297, 2009. cited
By 12.
[7] J.-P. Duval and A. Lefebvre. Words over an ordered
alphabet and suﬃx permutations. Theoretical Informatics and Applications, 36(3):249–259, 2002. cited By
19.
[8] Jean-Pierre Duval, Thierry Lecroq, and Arnaud Lefebvre. Border array on bounded alphabet. J. Autom.
Lang. Comb., 10(1):51–60, January 2005.
[9] M. Fredman and M. Saks. The cell probe complexity of
dynamic data structures. In Proceedings of the Twentyfirst Annual ACM Symposium on Theory of Computing, STOC ’89, pages 345–354, New York, NY, USA,
1989. ACM.
[10] Bernard A. Galler and Michael J. Fisher. An improved
equivalence algorithm. Commun. ACM, 7(5):301–303,
May 1964.
[11] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-

[17]
[18]

[19]

[20]

[21]

[22]

9

Completeness. W. H. Freeman & Co., New York, NY,
USA, 1979.
P. Gawrychowski, A. Jez, and L. Jez. Validating the
knuth-morris-pratt failure function, fast and online.
Theory of Computing Systems, 54(2):337–372, 2014.
cited By 7.
Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and
Masayuki Takeda. Counting parameterized border arrays for a binary alphabet. In Language and automata
theory and applications, volume 5457 of Lecture Notes
in Comput. Sci., pages 422–433. Springer, Berlin, 2009.
Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and
Masayuki Takeda. Verifying and enumerating parameterized border arrays. Theoretical Computer Science,
412(50):6959 – 6981, 2011.
Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and
Masayuki Takeda.
Verifying and enumerating parameterized border arrays. Theoret. Comput. Sci.,
412(50):6959–6981, 2011.
Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and
Masayuki Takeda. Inferring strings from suﬃx trees
and links on a binary alphabet. Discrete Applied Mathematics, 163, Part 3:316 – 325, 2014. Stringology Algorithms.
Kevin Knight. Uniﬁcation: A multidisciplinary survey.
ACM Comput. Surv., 21(1):93–124, March 1989.
Gregory Kucherov, Lilla Tóthmérész, and Stéphane
Vialette. On the combinatorics of suﬃx arrays. Information Processing Letters, 113(22–24):915 – 920, 2013.
Weilin Lu, P. J. Ryan, W. F. Smyth, Yu Sun, and
Lu Yang. Verifying a border array in linear time. J.
Comb. Math. Comb. Comput, 42:223–236, 2000.
Ross M. McConnell, Kurt Mehlhorn, Stefan Näher, and
Pascal Schweitzer. Certifying algorithms. Computer
Science Review, 5(2):119–161, 2011.
Tatiana Starikovskaya and Hjalte Wedel Vildhøj. A
suﬃx tree or not a suﬃx tree? Journal of Discrete
Algorithms, 32:14 – 23, 2015. StringMasters 2012 2013
Special Issue (Volume 2).
Robert Endre Tarjan. Eﬃciency of a good but not linear set union algorithm. J. ACM, 22(2):215–225, April
1975.

s: r

t: y

r
y

x

x

y

y

z

z

r

r

x

z

x
z

(a) Trees s and t

(b) t′ = merge(s, t)

(c) t′′ = push(t′ , x, y)

(d) t′′′ = collapse(t′′ , z)

Figure 1: Merge, collapse and push.

Figure 2: A flat tree with H = 9, K = 3. The six depth-one light nodes’ sizes sum up to 4 × 9 = 36.

Figure 3: Illustrating the reduction: t(I) for I = (5, 5, 5, 5, 5, 6, 6, 7, 7), m = 3, B = 17. Then D = 4, d = 1
and H = 24. Small weights wij are of size 1, 2, 4.

Figure 4: The Union tree corresponding to a solution of the instance on Figure 3.

10

