Lowest common manager in an org chart

A company's reporting structure is a rooted tree. Each person is an Employee with a unique name and a list reports of the people who report to them directly. The root is the CEO, and every other employee has exactly one direct manager.

Implement:

def lowest_common_manager(root: Employee, a: Employee, b: Employee) -> Employee

Return the lowest common manager of a and b: the employee farthest from the CEO whose reporting tree contains both of them. An employee counts as part of their own reporting tree, so if a manages b (directly or through others), the answer is a.

Constraints

• 1 <= number of employees <= 10^5. The tree may be very deep (a long single chain), so be careful with recursion depth.
• Each employee has any number of direct reports.
• Ask your interviewer whether a and b are guaranteed to be in the tree. If not, return None when either is missing.

Example 1

            Maya
          /  |   \
      Omar  Lin   Ravi
      /  \          |
   Ines  Theo      Kofi

• lowest_common_manager(Maya, Ines, Theo) returns Omar.
• lowest_common_manager(Maya, Theo, Kofi) returns Maya.

Example 2

Using the same tree, lowest_common_manager(Maya, Omar, Ines) returns Omar, because Omar manages Ines and counts as part of his own reporting tree.

Expect follow-ups such as finding the common manager of a whole group of employees, or answering many queries quickly on the same org chart.