Question :
Suppose you work for a company, iPuritan.com, that has strict rules for when two employees, x and y, may date one another, requiring approval from their lowest-level common supervisor.
The employees at iPuritan.com are organized in a tree, T, such that each node in T corresponds to an employee and each employee, z, is considered a supervisor for all of the employees in the subtree of T rooted at z (including z itself).
The lowest-level common supervisor for x and y is the employee lowest in the organizational chart, T, that is a supervisor for both x and y.
Thus, to find a lowest-level common supervisor for the two employees, x and y, you need to find the lowest common ancestor (LCA) between the two nodes for x and y, which is the lowest node in T that has both x and y as descendants (where we allow a node to be a descendant of itself).
Given the nodes corresponding to the two employees x and y, describe an efficient algorithm for finding the supervisor who may approve whether or not x and y may date each other, that is, the LCA of x and y in T.
What is the running time of your method?