Algorithm for enumerating unique ways to remove leaves from a tree?

Question

I am looking at this challenge:

Consider a tree graph, where each vertex can be removed only if it is a leaf node. A parent node may have multiple children nodes. A root node is given, which, as implied by the rule can only be removed when all its subtrees are removed. A choice also exists to not remove any node whatsoever. Directed edge (𝑢,𝑣) indicates that 𝑢 is the parent of 𝑣. The algorithm should return the number of such options and the options themselves for a given tree.

I tried to find some optimal substructure for it but I couldn't find one. The leaves contribute 2^𝑛 options as we can choose to delete or not delete them. If a node has m children then it adds 𝑚2^𝑛−1+1 to the above layer's choice count, almost, I can't find a correct relation.

Answer 1

The structure that you should be looking forward to is this. Suppose that a node N has children C1, C2, ..., Cn. Also suppose that options(node) is how many ways there are to do your removal from node.

Then options(N) = options(C1) * options(C2) * ... * options(Cn) + 1. Why? The first term is because you can independently choose any way of removing below each child. And then +1 because you can remove the entire subtree, including N itself.

To actually generate them, just iterate through the product of the options for each child, and then include "everything".

---

Here is a solution for getting all of the subsets. I admit that I didn't wind up using caching where I thought I might.

# A trivial tree implementation.
class Tree:
    def __init__ (self, label):
        self.label = label
        self.children = []

    def add_subtree (self, branch):
        self.children.append(branch)

    def all_labels (self):
        answer = [self.label]
        for child in self.children:
            answer = answer + child.all_labels()
        return answer

# We will be working with iter functions that:
#
#   - take an initial list of values.
#   - yield lists that start with that list of values.
#
# Here is a trivial example.
def empty_list_iter (initial):
    yield initial

# We will be doing higher order programming on these iter functions.
#
# That is, we will be using iter functions as data. This one gives
# all combinations from two iter functions. Each yielded list will
# have list a data followed by list b data.
def comb_iter_func (iter_func_a, iter_func_b):
    def comb_iter (initial):
        for next_initial in iter_func_a(initial):
            yield from iter_func_b(next_initial)
    return comb_iter

# Let's do the same for an arbitrary list of functions.
def product_iter_func (iter_funcs):
    if 0 == len(iter_funcs):
        # This is exactly analogous to an empty product returning 1.
        return empty_list_iter
    elif 1 == len(iter_funcs):
        return iter_funcs[0]
    else:
        # Recursively combine them.
        mid = len(iter_funcs) // 2
        return comb_iter_func(
                product_iter_func(iter_funcs[0:mid]),
                product_iter_func(iter_funcs[mid:]))

def removable_node_set_iter_func(tree):
    # This will iterate through all combinations of children.
    children_iter_func = product_iter_func(
            [removable_node_set_iter_func(child)
                for child in tree.children])

    # Here is the iter_func we will return.
    def this_iter (initial):
        # All things in the product of the children.
        yield from children_iter_func(initial)
        # The whole tree.
        yield initial + tree.all_labels()

    return this_iter

# Now our actual iter.
def removable_node_set_iter(tree):
    this_func = removable_node_set_iter_func(tree)
    yield from this_func([])

And here is a quick test of it in acction.

# Now let's build a tree to test it on.
trees = [Tree(i) for i in range(6)]

# root 0. Children 1, 3. 2 is below 1. And 4,5 split below 3.
for parent, child in [(0, 1), (1, 2), (0, 3), (3, 4), (3, 5)]:
    trees[parent].add_subtree(trees[child])

for removable in removable_node_set_iter(trees[0]):
    print(removable)

Answer 2

I would first solve the complementary problem, i.e. generating all possible subtrees that include the root node. The values that are not in such subtree constitute a set of values you are looking for.

To generate all subtrees that include a given root, you would take all possible subsets of its direct children, i.e. the powerset of its children, and for each child in one such combination you solve the problem recursively, giving you all possible subtrees for that child. Apply a Cartesian product on the sets of subtrees you got for each child in a given combination to build one unique subtree (adding the root).

From these results, get the complementary results by subtracting every set of values from the set of all values.

Below two implementations:

1. JavaScript implementation

Here I included definitions of generic functions (like powerset, product, ...), using generators. But you can obviously turn these generators to simple array-returning functions if you wanted to.

class Node {
    constructor(value, ...children) {
        this.value = value;
        this.children = children;
    }
}

// Produce all subsets of given unique values
function* powerset(arr) {
    if (arr.length == 0) {
        yield [];
    } else {
        for (const subseq of powerset(arr.slice(1))) {
            yield subseq;
            yield [arr[0], ...subseq];
        }
    }
}

// Produce Cartesian product of given arrays
function* product(arrays) {
    if (arrays.length == 0) {
        yield [];
    } else {
        for (const rest of product(arrays.slice(1))) {
            for (const item of arrays[0]) {
                yield [item, ...rest];
            }
        }
    }
}

// Get the flattened elements from the given arrays
function* flatten(arrays) {
    for (const item of arrays) yield item.flat();
}

// Main algorithm: generate all possible, non-empty subtrees with given root
function* allSubtreeValues(root) {
    yield [root.value];
    for (const childSelection of powerset(root.children)) {
        const subtrees = childSelection.map(child => Array.from(allSubtreeValues(child)));
        for (const selected of flatten(product(subtrees))) {
            if (selected.length) yield [root.value, ...selected];
        }
    }
}

// Gets all values present in a given tree
function* allValues(root) {
    if (!root) return;
    yield root.value;
    for (const child of root.children) yield* allValues(child);
}

// Subtracts values from a given array with unique values.
function difference(a, b) {
    const exclude = new Set(b);
    return a.filter(val => !exclude.has(val));
}

// Function that gets the complementary values from allSubtreeValues()
function* allLeafPluckSets(root) {
    const all = Array.from(allValues(root));
    yield all;
    for (const subtreeValues of allSubtreeValues(root)) {
        yield difference(all, subtreeValues);
    }
}

// Demo
console.log("Example 1:");
const root = // continues below...
new Node(1,
    new Node(2, 
        new Node(4)
    ),
    new Node(3, 
        new Node(5)
    )
);
for (const values of allLeafPluckSets(root)) 
    console.log(JSON.stringify(values));

console.log("Example 2:");
const root2 = // continues below...
new Node(1,
    new Node(2, 
        new Node(3,
            new Node(4), 
            new Node(5)
        )
    )
);
for (const values of allLeafPluckSets(root2)) 
    console.log(JSON.stringify(values));

2. Python implementation

Here is a similar implementation, but in Python, making use of some itertools and more_itertools functions:

from itertools import product
from more_itertools import powerset, flatten

class Node:
    def __init__(self, value, *children):
        self.value = value
        self.children = children

# Get all the values in the given tree
def all_values(root):
    if root:
        yield root.value
        for child in root.children:
            yield from all_values(child)

# Main algorithm: get all possible subtrees (their values) with this root
def all_subtree_values(root):
    yield [root.value]
    for child_selection in powerset(root.children):
        subtrees = [
            list(all_subtree_values(child))
            for child in child_selection
        ]
        for selected in product(*subtrees):
            if selected:
                yield [root.value, *flatten(selected)]

# Get all the subtrees, but now produce the values NOT in a subtree
def all_leaf_pluck_sets(root):
    values = set(all_values(root))
    yield values
    for subtreeValues in all_subtree_values(root):
        yield values.difference(subtreeValues)

Example use:

# Example 1
root = Node(1,
    Node(2, 
        Node(4)
    ),
    Node(3, 
        Node(5)
    )
)
for values in all_leaf_pluck_sets(root):
    print(values)

# Example 2
root = Node(1,
    Node(2, 
        Node(3,
            Node(4), 
            Node(5)
        )
    )
)
for values in all_leaf_pluck_sets(root):
    print(values)