# How can I get all representations of an n-ary tree that completely “cover” the tree?

I have an n-ary tree and I want to get all possible representations of the tree that "cover" (for lack of a better term) the tree. Here's what I mean by cover:

Suppose we have the following tree

        1
/    \
2      3
/ \    /|\
4   6  5 7 8
|
9


I want to somehow obtain the following:

• 1
• 2, 3
• 2, 5, 7, 8
• 4, 6, 3
• 4, 6, 5, 7, 8
• 4, 9, 3
• 4, 9, 5, 7, 8

As you can see 1 completely covers the tree because all leaves are underneath it. Similarly 2, 3 covers the entire tree because all leaves are underneath them. This goes for all of them until finally we get to 4, 9, 5, 7, 8 which covers the entire tree because all leaves are underneath (or are them).

Is there an algorithm to do this or a modification of a classic search algorithm that will produce this?

• I have figured out a crummy recursive way to do this, I will post it below tomorrow afternoon when I get a chance. – Nick Chapman Mar 9 '17 at 6:56

Let $T$ be a tree with root $r$, and let the children of $r$ be $r_1,\ldots,r_d$. Then every minimal cover of $T$ either consists of $r$, or is a union of minimal covers of $r_1,\ldots,r_d$; if $r$ is a leaf then the second option doesn't exist. You can easily convert this to a recursive algorithm that lists all minimal covers.

Yuval was moving in the right direction.

Here's the pseduo code:

def get_tree_covers(node):
node_covers = []
if node is NULL:
return node_covers
node_covers.append(node.value)
if node.children is NULL:
return node_covers
child_covers = [] // Used to store the covers of each child
for child in node.children:
child_covers.append(get_tree_covers(child))
if child_covers.length == 1:
tree_covers = join_lists(tree_covers, child_covers[0])
return tree_covers
joined_covers = child_covers[0]
for i in range(1 to child_covers.length):
new_tree_covers = []
for j in range(0 to joined_covers.length):
for k in range(0 to child_covers[i]):
new_cover = joined_covers[j] + child_covers[i][k]
new_tree_covers.append(new_cover)
joined_covers = new_tree_covers
tree_covers = join_lists(tree_covers, joined_covers)
return tree_covers


The runtime is abysmal and I would love to know if anyone can come up with anything quicker. Worst case this thing runs in O(max_branch_lengh^number_of_branches) which is really bad. For my use case it works out all right because I'm using it on very small trees so we're talking at most a few hundred operations. But on a larger tree this would really kill your runtime.

• I'm not sure that the running time is abysmal in the number of covering representations. – Yuval Filmus Mar 11 '17 at 12:57
• @YuvalFilmus what do you mean in the number of covering representations? – Nick Chapman Mar 12 '17 at 0:37
• I mean the size of the output. – Yuval Filmus Mar 12 '17 at 10:01