Suppose you work for a company iPuritancom that has strict r

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?

Solution

Here the concern is to have a communication among nodes. Before establishing the communication immediate root node is to be visited for permission.

Effectively for B+ kind of tree where node to node communication is possible, efficiency in (nlogn), but extra efforts are needed to find permission from ancestor which is nothing but n.

So for tree T of three nodes, one parent node is to be visited which require total three transactions which is nothing but n.