Minimum subtree containing nodes from set

Question

There is a tree structure, e.g.

   1
  / \
 /   \
2     3
|    / \
|   /   \
4  5     6

and set of nodes (leafs), that must be in subtree, e.g.

[5, 6]

How to find minimum subtree that contains all these nodes and begins from root element? Like this:

   1
    \
     \
      3
     / \
    /   \
   5     6

Answer 1

Basically, you can recurse down to the leaves, and find, for each leaf, whether it is needed or not. When the recursion goes back up again, you can see if any of the descendants was needed.

Here is pseudo-code that does this:

def mark_needed_nodes(node, given_nodes):
    # If a leaf, check if it is in given_nodes
    if node is leaf:
        node.needed = node in given_nodes
        return node.needed

    # It is not a leaf; check if any of the descendants is needed.
    node.needed = False
    for child in node.children:
        node.needed = needed or mark_needed_nodes(child, given_nodes)
    return node.needed

You would call mark_needed_nodes(root, given_nodes).

---

Assuming given_nodes is a hash-based dictionary, the complexity is linear in the number of nodes in the tree.