LCA - Lowest Common Ancestor
The lowest common ancestor (LCA) is a concept in graph theory and computer science.

Let ‘T’ be a rooted tree with ‘N’ nodes. The lowest common ancestor is defined between two nodes, ‘u’ and ‘v’, as the lowest node in ‘T’ that has both ‘u’ and ‘v’ as descendants (where we allow a node to be a descendant of itself). - Wikipedia

For the given tree, The LCA of nodes 5 and 8 will be node 2, as node 2 is the first node that lies in the path from node 5 to root node 1 and from node 8 to root node 1.

Path from node 5 to root node looks like 5 → 2 → 1.

Path from node 8 to root node looks like 8 → 6 → 2 → 1.

Since 2 is the first node that lies in both paths. Hence LCA will be 2.

Given any two nodes ‘u’ and ‘v’, find the LCA for the two nodes in the given Tree ‘T’.

Note: For each test case, the tree is rooted at node 1.

Input Format-

The first line contains an integer ‘T’ which denotes the number of test cases. For each test case: The first line contains a single integer ‘N’, denoting the number of nodes. Each of the following ‘N’ - 1 line contains two space-separated integers, ‘ui’ and ‘vi’, which means an edge connects these two nodes. The following line will contain a single integer ‘Q’, denoting the number of queries you have to answer for the given tree. In the following ‘Q’ lines, each one will have two numbers, ‘u’ and ‘v’, for which you have to find the LCA of ‘u’ and ‘v’.

Output Format-

Your task is to print ‘Q’ lines for each test case. The ‘Q’ lines should be the LCA of the given ‘u’ and ‘v’, respectively.

Constraints -

1

Question

LCA - Lowest Common Ancestor

The lowest common ancestor (LCA) is a concept in graph theory and computer science.

Let ‘T’ be a rooted tree with ‘N’ nodes. The lowest common ancestor is defined between two nodes, ‘u’ and ‘v’, as the lowest node in ‘T’ that has both ‘u’ and ‘v’ as descendants (where we allow a node to be a descendant of itself). - Wikipedia

For the given tree, The LCA of nodes 5 and 8 will be node 2, as node 2 is the first node that lies in the path from node 5 to root node 1 and from node 8 to root node 1.

Path from node 5 to root node looks like 5 → 2 → 1.

Path from node 8 to root node looks like 8 → 6 → 2 → 1.

Since 2 is the first node that lies in both paths. Hence LCA will be 2.

Given any two nodes ‘u’ and ‘v’, find the LCA for the two nodes in the given Tree ‘T’.

Note: For each test case, the tree is rooted at node 1.

Input Format-

The first line contains an integer ‘T’ which denotes the number of test cases. 

For each test case:
The first line contains a single integer ‘N’, denoting the number of nodes.
Each of the following ‘N’ - 1 line contains two space-separated integers, ‘ui’ and ‘vi’, which means an edge connects these two nodes.

The following line will contain a single integer ‘Q’, denoting the number of queries you have to answer for the given tree.  
In the following ‘Q’ lines, each one will have two numbers, ‘u’ and ‘v’, for which you have to find the LCA of ‘u’ and ‘v’.

Output Format-

Your task is to print ‘Q’ lines for each test case. 
The ‘Q’ lines should be the LCA of the given ‘u’ and ‘v’, respectively.

Constraints -

1<= ‘T' <= 5  
1 <= ‘N’ <= 10^5
1 <= ‘Q’ <= 10^5.
1 <= ‘u’, ‘v’ <= ‘N’.

Time Limit: 1 sec

Accepted Answer

I used the concept of recursion in trees and solved the probelm with O(n) complexity.
Search through the left and right subtrees and return answer.

The node which has one key present in its left subtree and the other key present in the right subtree is the LCA. If both keys lie in the left subtree, then the left subtree has LCA also, otherwise, LCA lies in the right subtree.

Accepted Answer

Brute Force

Prerequisite - DFS

Approach:

We will store the depth and the direct parent of each node using a dfs.

Now, if we have to find the LCA to two nodes, first we would move upward the node which has a higher depth until both the nodes reach the same depth, then we will move both the node upward until they become the same, the node that we reach will be the LCA.

Algorithm:

Initialize two arrays of length ‘N + 1’ to store depth and the direct parent of each node.

Func dfs(cur, parent):
- Update depth[cur] to depth[parent] + 1.
- Update par[cur] to parent
- Iterate in all the children of node ‘cur’ and call dfs as dfs(child, cur)

Func get_lca(u, v):
- While depth[u] > depth[v]:
  - Update u to par[u]
- While depth[v] > depth[u]:
  - Update v to par[v]
- While u != v:
  - Update u to par[u]
  - Update v to par[v]
- Return u
Func Main():
- dfs(1, 0)
- For u,v in query:
  - print(get_lca(u, v))

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of nodes of the tree.

We are creating two arrays of length ‘N + 1’. Hence overall complexity will be O(N).

Time Complexity: OtherExplanation:

O(N * Q). Where ‘N’ is the number of nodes, and ‘Q’ is the number of queries.

We might use the while loop for each query for a total of ‘N’ time in the worst case. Hence overall complexity is O(N * Q).

Java (SE 1.8)

/*

    Time Complexity: O(Q * N).

    Space Complexity: O(N)



    where 'N' is the number of nodes, and 'Q' is the number of queries.

*/



import java.util.*;

public class Solution {



    public static int MAX_N = 100010;

    public static ArrayList[] graph= new ArrayList[MAX_N];

    public static int[] par = new int[MAX_N];

    public static int[] depth = new int[MAX_N];



    // To find the depth and filling the sparse table of each node.

    public static void dfs(int cur, int parent){

        par[cur] = parent;

        depth[cur] = depth[parent] + 1;

        

        // Iterating in the childs of the node.

        for(int i = 0; i < graph[cur].size(); i++)

        {

            // Checking if it is not the parent.

            if(graph[cur].get(i) != parent)

            {

                dfs(graph[cur].get(i), cur);

            }

        }

    }

    public static int get_lca(int u, int v){

       // Moving the node which has higher depth, until both of the node to have the same depth.

        while(depth[u] > depth[v])

        {

            u = par[u];

        }

        while(depth[v] > depth[u])

        {

            v = par[v];

        }

        // Moving both the node up, until they reach the same node.

        while(u != v)

        {

            u = par[u];

            v = par[v];

        }

        return u;

    

    }



    public static int[] lca(int n, int[][] edge, int[][] query) {

        

        // Initilizating all the arrays to its default value.

        for (int i = 0; i < n + 1; ++i)

        {

            graph[i] = new ArrayList();

            depth[i] = 0;

            par[i] = 0;

        }

        

        // Making the adjacency list.

        for(int i = 0; i < edge.length; i++)

        {

            graph[edge[i][0]].add(edge[i][1]);

            graph[edge[i][1]].add(edge[i][0]);

        }



        dfs(1, 0);

        int[] ans = new int[query.length];

        for(int i = 0; i < query.length; i++)

        {

            ans[i] = get_lca(query[i][0], query[i][1]);

        }

        return ans;

    }

}

Python (3.5)

'''

    Time Complexity: O(Q * N).

    Space Complexity: O(N)



    where 'N' is the number of nodes, and 'Q' is the number of queries.

'''



def lca(n, edge, query):

    

    graph = [[] for i in range (n + 1)]

    par = [0] * (n + 1)

    depth = [0] * (n + 1)

    

    # Making the adjacency list.

    for u, v in edge:

        graph[u].append(v)

        graph[v].append(u)

        

    # To find the depth and direct parent of each node.

    def dfs(cur, parent):

        par[cur] = parent

        depth[cur] = depth[parent] + 1

        

        # Iterating in the childs of the node.

        for i in graph[cur]:

            # Checking if it is not the parent.

            if i != parent:

                dfs(i, cur)

                

    dfs(1, 0)

    

    def get_lca(u, v):

        # Moving the node which has higher depth, until both of the node to have the same depth.

        while depth[u] > depth[v]:

            u = par[u]

        while depth[v] > depth[u]:

            v = par[v]

            

        # Moving both the node up, until they reach the same node.

        while u != v:

            u = par[u]

            v = par[v]

            

        return u

    

    ans = []

    

    for u, v in query:

        ans.append(get_lca(u, v))

        

    return ans

C++ (g++ 5.4)

/*

    Time Complexity: O(Q * N).

    Space Complexity: O(N)



    where 'N' is the number of nodes, and 'Q' is the number of queries.

*/



// Initialization.

const int MAX_N = 1e5 + 10;

vector graph[MAX_N];

int par[MAX_N];

int depth[MAX_N];



// To find the depth and direct parent of each node.

void dfs(int cur, int parent)

{

    par[cur] = parent;

    depth[cur] = depth[parent] + 1;

    

    // Iterating in the childs of the node.

    for (auto& i : graph[cur])

    {

        // Checking if it is not the parent.

        if(i != parent)

        {

            dfs(i, cur);

        }

    }

}



int get_lca(int u, int v)

{

    

    // Moving the node which has higher depth, until both of the node to have the same depth.

    while(depth[u] > depth[v])

    {

        u = par[u];

    }

    while(depth[v] > depth[u])

    {

        v = par[v];

    }

    // Moving both the node up, until they reach the same node.

    while(u != v)

    {

        u = par[u];

        v = par[v];

    }

    return u;

}



vector lca(int n, vector> edge, vector> query)

{

    // Initilizating all the arrays to its default value.

    for (int i = 0; i < n + 1; ++i)

    {

        graph[i].clear();

        depth[i] = 0;

        par[i] = 0;

    }

    // Making the adjacency list.

    for (auto& i : edge)

    {

        graph[i[0]].push_back(i[1]);

        graph[i[1]].push_back(i[0]);

    }



    dfs(1, 0);

    vector ans;

    for (auto& i : query)

    {

        ans.push_back(get_lca(i[0], i[1]));

    }

    return ans;

}

Accepted Answer

Binary Lifting

Prerequisite - Sparse Table, DFS

Approach:

Using Sparse Table, we can efficiently find the kth ancestor of any node in the tree in O(log(N)). Using this, we can divide the problem of finding the LCA into two parts. We use two pointers that initially point to the two nodes whose LCA we have to find.

Let’s take an example:

We have to find the LCA of nodes ‘4’ and ‘5’.

The black circle around the nodes denote the current positions of both the pointers.

Initially, both point to initial nodes which are node ‘4’ and node ‘5’.

Now, one of the pointers moves upwards so that both pointers point to nodes at the same level. I.e. we will move our pointer upward, which has a higher depth until both of the pointers reach the same depth. This can be done in O(log(N)) by using a sparse table.

After this, we determine the minimum number of steps needed to move both pointers upwards to point to the same node. The node to which the pointers point after this is the lowest common ancestor.

The example suffices to move both pointers one step upwards to node 1, which is the lowest common ancestor.

Algorithm:

Initialize a variable ‘level’ to log(N) + 3;

Initialize a 2d array ‘dp’ of dimension ‘(N + 1) * level’ to find the ‘kth’ ancestor of any tree node using the sparse table technique.

Initialize an array ‘depth’ of length ‘N + 1’ to store the depth of all the nodes from root node 1.

Func dfs(curr, par)
- Update dp[cur][0] to par.
- Update depth[cur] to depth[par] + 1.
- Run a for loop from i = ‘1’ to ‘level’. → standard filling of a sparse table
  - If dp[cur][i - 1] is not ‘0’.
    - Update dp[cur][i] to dp[dp[cur][i - 1]][i -1].
- Iterate in all the children of node ‘cur’ and call dfs as dfs(child, cur)
Func get_lca(u, v):
- Swap ‘u’ and ‘v’ if the depth of node ‘u’ is greater than node ‘v.’,I.e. if depth[u] > depth[v] swap(u, v)
- Initilaze a variable dis equals to depth[v] - depth[u].
- Run a for loop from i = ‘0’ to ‘level’. → making both the nodes at the same depth.
  - If ‘ith’ bit in ‘dis’ is set i.e. d & (1 << i) == 1.
    - Update ‘v’ to dp[v][i]
- If node ‘u’ and ‘v’ are the same, return ‘u’ as we have found the LCA.
- Run a for loop from i = ‘level - 1’ to ‘0’.
  - If (2 ^ i)th parent of ‘u’ and ‘v’ is same, i.e. dp[u][i] == dp[v][i],
    - We do nothing
  - Else
    - We update ‘u’ to dp[u][i]
    - We update ‘v’ to dp[v][i]
- We return parent of ‘u’, i.e. dp[u][0].

Func Main():

dfs(1, 0)
For each query
- Print get_lca(u, v)

Space Complexity: O(nlogn)Explanation:

O(N * log(N)), where N is the number of nodes of the tree.

We are creating a 2-D array of size N * log(N). Hence overall complexity is O(N * log(N)).