4.6 LCA VI

Given m nodes in a K-nary tree, find their lowest common ancestor.

Assumptions: m >= 2. No parent pointer. Given m nodes are guaranteed to be in tree.

Input: KnaryTreeNode root, List<KnaryTreeNode> nodes

Output: KnaryTreeNode LCA if exists.

Solution:

1. Combination of 4.4 + 4.5

2. Base case: if root == null || set.contains(root), return root

3. Recursive rule: for each child of root, LCA(child, one, two)

if 2 children return not null, return root

if exactly one child return not null, return the return value from the child

if none return not null, return null

public KnaryTreeNode LCA(KnaryTreeNode root, List<KnaryTreeNode> nodes) {
  Set<KnaryTreeNode> set = new HashSet<>(nodes);
  return helper(root, set);
}

private KnaryTreeNode helper(KnaryTreeNode root, Set<KnaryTreeNode> set) {
  if (root == null || set.contains(root)) { return root; }
  KnaryTreeNode found = null;
  for (KnaryTreeNode child : root.children) {
    KnaryTreeNode node = helper(child, set);
    if (node == null) { continue; }
    if (found == null) {
       found = node;
    } else {
       return root;
    }
  }
  return found;
}