Lowest Common Manager

• Time : O(n)
• Space : O(nlogd)

using namespace std;

class OrgChart {
public:
    char name;
    vector<OrgChart *> directReports;

    OrgChart(char name) {
        this->name = name;
        this->directReports = {};
    }

    void addDirectReports(vector<OrgChart *> directReports);
};

struct LCAContext {
    int id = 0, maLvl = 0;
    unordered_map<int, OrgChart*> idmp;
    unordered_map<OrgChart*, int> ridmp;
    vector<int> lvl;
    vector<vector<int>> LCA = vector<vector<int>>(1000, vector<int>(22, -1));
    
    LCAContext() {}
};

void dfs(OrgChart* node, LCAContext& ctx, int depth = 0, int par = -1) {
    if(!node) return;
    int me = ctx.id;
	
    ctx.LCA[me][0] = par;
    ctx.maLvl = max(ctx.maLvl, depth);
    ctx.ridmp[node] = ctx.id;
    ctx.idmp[ctx.id++] = node;
    ctx.lvl.push_back(depth);
    for(auto& child : node->directReports) {
        dfs(child, ctx, depth + 1, me);
		}
}

void update(LCAContext& ctx) {
    int n = ctx.id, m = log2(ctx.maLvl) + 1;
    for(int j = 0; j < 21; j++) {
        for(int i = 0; i < n; i++) {
            ctx.LCA[i][j+1] = ctx.LCA[ctx.LCA[i][j]][j];
        }
    }
}

int query(int u, int v, LCAContext& ctx) {
	cout<<ctx.lvl[u]<<' '<<ctx.lvl[v]<<endl;
    if(ctx.lvl[u] < ctx.lvl[v]) swap(u, v);
    int diff = ctx.lvl[u] - ctx.lvl[v];
    for(int j = 0; diff; j++, diff /= 2) {
        if(diff & 1) u = ctx.LCA[u][j];
    }
    if(v != u) {
        for(int j = 20; j >= 0; j--) {
            if(ctx.LCA[u][j] != ctx.LCA[v][j]) {
							cout<<u<<' '<<v<<endl;
                u = ctx.LCA[u][j];
                v = ctx.LCA[v][j];
							cout<<ctx.lvl[u]<<' '<<ctx.lvl[v]<<endl;
            }
        }
        u = ctx.LCA[u][0];
    }
    return u;
}

OrgChart *getLowestCommonManager(OrgChart *topManager, OrgChart *reportOne,
                                 OrgChart *reportTwo) {
    LCAContext ctx;
    dfs(topManager, ctx);
    update(ctx);
    return ctx.idmp[query(ctx.ridmp[reportOne], ctx.ridmp[reportTwo], ctx)];
}

• Time : O(n)
• Space : O(1)

using namespace std;

class OrgChart {
public:
  char name;
  vector<OrgChart *> directReports;

  OrgChart(char name) {
    this->name = name;
    this->directReports = {};
  }

  void addDirectReports(vector<OrgChart *> directReports);
};

pair<int, OrgChart*> helper(OrgChart* node, OrgChart* A, OrgChart* B) {
	if(!node) return {0, nullptr};

	int hasCount = 0;
	OrgChart* pointer = nullptr;
	if(node == A) hasCount++;
	if(node == B) hasCount++;
	
	for(auto& child : node->directReports) {
		auto [has, po] = helper(child, A, B);
		hasCount += has;
		if(po != nullptr) return {hasCount, po};
	}
	
	if(hasCount == 2)
		return {2, node};
	return {hasCount, nullptr};
}

OrgChart *getLowestCommonManager(OrgChart *topManager, OrgChart *reportOne,
                                 OrgChart *reportTwo) {
  auto [_, res] = helper(topManager, reportOne, reportTwo);
  return res;
}