Here is the LCA implementation using binary lifting:
function companyQueriesII(n, parent, queries):
LOG = ceil(log2(n))
up = 2D array of size n x LOG
depth = array of size n
// Build sparse table
for i from 1 to n:
up[i][0] = parent[i]
for j from 1 to LOG - 1:
for i from 1 to n:
if up[i][j-1] != -1:
up[i][j] = up[up[i][j-1]][j-1]
// Compute depths with BFS from root
computeDepths()
function lca(a, b):
if depth[a] < depth[b]:
swap(a, b)
// Bring a to same depth as b
diff = depth[a] - depth[b]
for j from 0 to LOG - 1:
if diff & (1 << j):
a = up[a][j]
if a == b:
return a
// Binary lift both until they meet
for j from LOG - 1 down to 0:
if up[a][j] != up[b][j]:
a = up[a][j]
b = up[b][j]
return up[a][0]
for (a, b) in queries:
print lca(a, b)
Time: preprocessing, per query. Space: .