[Python][Interview] LCA of M nodes in an N-ary Tree
Posting this as I got this question in an interview\nFind the LCA of m nodes in an n-ary tree, which can be reworded to find the smallest subtree of all m nodes
Posting this as I got this question in an interview\nFind the LCA of m nodes in an n-ary tree, which can be reworded to find the smallest subtree of all m nodes.\n\nKeep a count of the m nodes found in each subtree. Once count == len(m) this is the LCA and return the ans\n\nExample:\nm = `2,1,3` -> LCA is 5\nm = `7,3` -> 1\nm = `1,3` -> 1\nm = `1,3,6` -> 5\n\n```    \n\t5\n /   |  \\\n2    1    6\n    /    \\\n   7     3\ndef soln(root, m):\n    return recurse(root, m)[1]\n\ndef recurse(node, m):\n    if not node:\n        return (0, None) #return the count of m nodes seen and ans\n    \n    count = 0\n    ans = None\n    for child in node.children:\n        seen, prev = self.recurse(child, m)\n        if seen == -1:\n            # this means we have already foundthe ans\n            return (-1, prev)\n        ans = prev\n        count+=seen\n    \n    if node in m:\n        count+=1\n        prev = node # use this node now as LCA\n        \n    if count == len(m):\n        return (-1, root)\n    return (count, prev)\n```
['Depth-First Search', 'Python']