Lowest Common Ancestor LCA in N-ary Tree

Problem

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 –

public static class Employee {

        private final int id;
        private final String name;
        private final List<Employee> reports;

        public Employee(int id, String name) {
            this.id = id;
            this.name = name;
            this.reports = new ArrayList<Employee>();
        }

        /**
     * @return an integer ID for this employee, guaranteed to be unique.
     */
        public int getId() {
            return id;
        }

        /**
     * @return a String name for this employee, NOT guaranteed to be unique.
     */
        public String getName() {
            return name;
        }

        /**
     * @return a List of employees which report to this employee.  This list may be empty, but will
     *      never be null.
     */
        public List<Employee> getReports() {
            return reports;
        }

        /**
     * Adds the provided employee as a report of this employee. 
     */
    public void addReport(Employee employee) {
        reports.add(employee);
    }
}

Given two employees in a company, find the closest common boss of the two employees.

ImplementEmployee closestCommonManager(Employee e1, Employee e2)that will return closest common manager e1 and e2 directly or indirectly reports to.

Examples

           Bill (CEO)
       /        |    \
      DOM      SAMIR  MICHAEL
   /     \   \
 Peter   Bob Porter
 |    \
Milton Nina

For example, closestCommonManager(Milton, Nina) = Peter , closestCommonManager(Nina, Porter) = Dom, closestCommonManager(Nina, Samir) = Bill, closestCommonManager(Peter, Nina) = Peter, etc.

Definition

Lowest Common Ancestor Definition

Solution

Method 1 - DFS

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 here - Lowest Common Ancestor LCA in a Binary Tree. We also solved it in an iterative manner using parent pointer - Lowest Common Ancestor LCA in a Binary Tree Given 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. This is same as Lowest Common Ancestor of a Binary Tree#Method 2 - By Storing root to p and q paths using backtracking.

Code

Java

public Employee closestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee) {
	Stack<Employee> firstPath = new Stack<Employee>();
	Stack<Employee> secondPath = new Stack<Employee>();

	Employee root = ceo;

	DFS(root, firstEmployee, firstPath);
	DFS(root, secondEmployee, secondPath);

	if (firstPath.peek().getId() == firstEmployee.getId() && secondPath.peek().getId() == secondEmployee.getId()) {
		int size1 = firstPath.size();
		int size2 = secondPath.size();
		int diff = Math.abs(size2 - size1);

		if (size1 > size2) {
			moveUp(firstPath, diff);
		} else {
			moveUp(secondPath, diff);
		}

		while (firstPath.peek().getId() != secondPath.peek().getId()) {
			firstPath.pop();
			secondPath.pop();
		}

		if (firstPath.size() > 0) {
			return firstPath.pop();
		}
	}

	return null;
}


private boolean DFS(Employee root, Employee target, Stack<Employee> path) {
	path.push(root);

	if (root.getId() == target.getId()) {
		return true;
	}

	for (Employee r: root.getReports()) {
		boolean ans = DFS(r, target, path);

		if (ans) {
			return true;
		}
	}

	path.pop();

	return false;
}


private static void moveUp(Stack<Employee> path, int diff) {
	while (diff > 0 && !path.isEmpty()) {
		path.pop();
		diff--;
	}
}

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(n)

Lowest Common Ancestor LCA in N-ary Tree#

Problem#

Examples#

Definition#

Solution#

Method 1 - DFS#

Code#

Java#

Complexity#