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

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)