In a company which has CEO Bill and a hierarchy of employees. Employees can have a list of other employees reporting to them, which can themselves have reports, and so on. An employee with at least one report is called a manager.
Please implement the closestCommonManager method to find the closest manager (i.e. farthest from the CEO) to two employees. You may assume that all employees eventually report up to the CEO. Assume the following class which you can’t change –
Given two employees in a company, find the closest common boss of the two employees.
Bill --> CEO / | \ DOM SAMIR MICHAEL / \ \ Peter Bob Porter / \ Milton Nina
Employee closestCommonManager(Employee e1, Employee e2) that will return closest common manager e1 and e2 directly or indirectly reports to.
For example, closestCommonManager(Milton, Nina) = Peter , closestCommonManager(Nina, Porter) = Dom, closestCommonManager(Nina, Samir) = Bill, closestCommonManager(Peter, Nina) = Peter, etc.
How do we solve this problem? This should be straightforward enough to figure out that this is an LCA problem. We solved the LCA for binary trees in a previous post by a simple recursion. We also solved it in an iterative manner using parent pointer. However, in this problem we need to find LCA of two nodes in an n-array tree where a node can have zero or many children. It would be straightforward if we had a parent pointer, then we could have simply walked upward from the node toward the closest common anchestor. But in this problem, the node (Employee) doesn’t have a parent pointer. How do we solve it then?
Idea is same as finding the ancestor path from the node upward to the root. Instead of finding this path through parent pointers we can do a DFS traverse from root down to the node and save the path in upward fashion using a stack. Now, we will apply same technique described in here to find the LCA. First, we will walk upward along the longer path upto diff of the two paths. Then we traverse upward concurrently along both of the paths until a common parent is reached, which is in turn the LCA i.e. the common boss.
Below is the implementation if the above idea that runs in O(n) time and O(n) space.