Return to Answer

1. Eliminate redundancies from \$M\$ as described above.
2. For each node \$x\$ in the tree:
3. If \$C(x) ⊆ M\$ then:
4. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$
5. Go to step 2.

1. Eliminate redundancies from \$M\$.
2. For each node \$x\$ in post-order:
3. If \$C(x) ⊆ M\$ then:
4. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$

1. Eliminate redundancies from \$M\$.
2. Initialize a map \$K\$ from nodes to non-negative integers such that \$K(x) = |C(x) ∩ M|\$, the number of children of \$x\$ that are in the set of nodes to be compacted.
3. For each node \$x\$ in post-order:
4. If \$K(x) = |C(x)|\$ then:
5. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$
6. Update \$K(P(x))\$ to \$K(P(x)) + 1\$

1. Eliminate redundancies from \$M\$ as described above.
2. For each non-leaf node \$x\$ in the tree:
3. If \$C(x) ⊆ M\$ then:
4. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$
5. Go to step 2.

1. Eliminate redundancies from \$M\$.
2. For each non-leaf node \$x\$ in post-order:
3. If \$C(x) ⊆ M\$ then:
4. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$

1. Eliminate redundancies from \$M\$.
2. Initialize a map \$K\$ from nodes to non-negative integers such that \$K(x) = |C(x) ∩ M|\$, the number of children of \$x\$ that are in the set of nodes to be compacted.
3. For each non-leaf node \$x\$ in post-order:
4. If \$K(x) = |C(x)|\$ then:
5. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$
6. Update \$K(P(x))\$ to \$K(P(x)) + 1\$

1. Eliminate redundancies from \$M\$ as described above.
2. For each node \$x\$ in the tree:
3. If \$x ∉ M\$ and \$C(x) ⊆ M\$ then:
4. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$
5. Go to step 2.

1. Eliminate redundancies from \$M\$.
2. For each node \$x\$ in post-order:
3. If \$x ∉ M\$ and \$C(x) ⊆ M\$ then:
4. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$

1. Eliminate redundancies from \$M\$.
2. Initialize a map \$K\$ from nodes to non-negative integers such that \$K(x) = |C(x) ∩ M|\$, the number of children of \$x\$ that are in the set of nodes to be compacted.
3. For each node \$x\$ in post-order:
4. If\$x ∉ M\$ and \$K(x) = |C(x)|\$ then:
5. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$
6. Update \$K(P(x))\$ to \$K(P(x)) + 1\$

1. Eliminate redundancies from \$M\$ as described above.
2. For each node \$x\$ in the tree:
3. If \$C(x) ⊆ M\$ then:
4. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$
5. Go to step 2.

1. Eliminate redundancies from \$M\$.
2. For each node \$x\$ in post-order:
3. If \$C(x) ⊆ M\$ then:
4. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$

1. Eliminate redundancies from \$M\$.
2. Initialize a map \$K\$ from nodes to non-negative integers such that \$K(x) = |C(x) ∩ M|\$, the number of children of \$x\$ that are in the set of nodes to be compacted.
3. For each node \$x\$ in post-order:
4. If \$K(x) = |C(x)|\$ then:
5. Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$
6. Update \$K(P(x))\$ to \$K(P(x)) + 1\$

• \$n\$ is the number of nodes in the tree;
• \$M\$ is the set of nodes we want to compact;
• \$m = |M|\$, the initial number of nodes in \$M\$;
• \$C(x)\$ is the function that returns the set of children of the node \$x\$ in the tree.
• \$P(x)\$ is the function that returns the parent of the node \$x\$ in the tree.

Any algorithm for this problem is going to have to find nodes all of whose children node are present in the set of nodes to be compacted (that is, to find nodes \$x\$ where \$C(x) ⊆ M\$), and update the set of nodes accordingly.

• \$n\$ is the number of nodes in the tree;
• \$M\$ is the set of nodes we want to compact;
• \$m = |M|\$, the initial number of nodes in \$M\$;
• \$C(x)\$ is the set of children of the node \$x\$ in the tree.
• \$P(x)\$ is the parent of the node \$x\$ in the tree.

Any algorithm for this problem is going to have to find nodes all of whose children are in the set of nodes to be compacted (that is, to find nodes \$x\$ where \$C(x) ⊆ M\$), and update the set of nodes accordingly.