Lowest Common Manager

Tags

Lowest Common Manager

Category

Recursion

Difficulty

Hard

Problem Statement

Given an organizational tree (a tree where each node represents a manager with direct reports), and two employees represented as nodes in the tree, find the lowest common manager of those two employees. The lowest common manager is the deepest node in the tree that has both employees as descendants (where a node can be a descendant of itself).

Intuition

This is essentially the Lowest Common Ancestor (LCA) problem applied to an organizational hierarchy. The key insight is that if we traverse the tree bottom-up, the lowest common manager is the first node whose subtree contains both target employees. We can use a recursive approach where each subtree reports back how many of the two target employees it contains. The first node that sees both employees accounted for in its subtree (including itself) is the answer.

Approach

  1. Define a recursive helper that returns two pieces of information: the number of target nodes found in the subtree, and the lowest common manager if found.
  2. For each node, recursively process all of its direct reports.
  3. Sum up the count of important nodes found across all subtrees.
  4. If any child subtree already found the LCM (count of 2), propagate that result upward.
  5. Check if the current node itself is one of the two target employees; if so, increment the count.
  6. If the count reaches 2 at the current node for the first time, the current node is the lowest common manager.
  7. Return the count and the LCM (or null) back up the call stack.

Pseudocode

function getLowestCommonManager(topManager, reportOne, reportTwo):
    result = getOrgInfo(topManager, reportOne, reportTwo)
    return result.lowestCommonManager

function getOrgInfo(manager, reportOne, reportTwo):
    numImportantReports = 0
    for each directReport in manager.directReports:
        info = getOrgInfo(directReport, reportOne, reportTwo)
        if info.lowestCommonManager is not null:
            return info
        numImportantReports += info.numImportantReports

    if manager == reportOne or manager == reportTwo:
        numImportantReports += 1

    lowestCommonManager = manager if numImportantReports == 2 else null
    return { lowestCommonManager, numImportantReports }

Time & Space Complexity

  • Time: O(n) where n is the number of nodes in the organizational tree. Every node is visited exactly once.
  • Space: O(d) where d is the depth of the tree, due to the recursion call stack. In the worst case (a skewed tree), this is O(n).

Key Insights

  • The problem reduces to LCA on a general (non-binary) tree.
  • By returning both a count and a candidate answer, we can short-circuit as soon as the LCM is found, avoiding unnecessary traversal.
  • A node can be its own descendant, so if one target is an ancestor of the other, the ancestor is the LCM.
  • The bottom-up approach naturally finds the lowest common manager because deeper nodes are evaluated before their parents.

Edge Cases

  • One of the target employees is the top manager itself — the top manager is the LCM.
  • One target employee is a direct or indirect report of the other — the higher one is the LCM.
  • Both target employees are the same node — that node is the LCM.
  • The tree has only one node which is both targets — return that node.
  • Targets are in completely separate branches — the LCM is the root of the smallest subtree containing both branches.

Linked mentions