4.5 LCA V

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

Assumptions: No parent pointer. Given two nodes are guaranteed to be in the K-nary tree.

Input: KnaryTreeNode root, one, two

Output: KnaryTreeNode LCA if exists

Solution:

1. Base case: if root == null, return null. if root == one/two, return two/one

2. 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, KnaryTreeNode one, KnaryTreeNode two) {
  if (root == null || root == one || root == two) { return root; }
  KnaryTreeNode found = null;
  for (KnaryTreeNode child : root.children) {
    KnaryTreeNode node = LCA(child, one, two);
    if (node == null) { continue; }
    if (found == null) {  //return the return value from the child
        found = node; 
      } else {	// 2 children return not null
        return root;
      }
  }
  return found;
}