LCA para árboles generales o n-arios (enfoque de array dispersa DP)

En publicaciones anteriores, hemos discutido cómo calcular el ancestro común más bajo (LCA) para un árbol binario y un árbol de búsqueda binaria ( this , this y this ). Ahora veamos un método que puede calcular LCA para cualquier árbol (no solo para árboles binarios). Utilizamos la programación dinámica con el enfoque de array dispersa en nuestro método. Este método es muy útil y rápido cuando necesita responder múltiples consultas de LCA para un árbol. 

Requisitos previos:

1. SFD 
2. Conocimientos básicos de DP ( Esto y esto ) 
3. Consulta de rango mínimo (descomposición de raíz cuadrada y tabla dispersa)

Enfoque ingenuo:- O(n) 
El enfoque ingenuo para este cálculo LCA de árbol general será el mismo que el enfoque ingenuo para el cálculo LCA del árbol binario (este enfoque ingenuo ya se describe bien aquí .

La implementación para el enfoque ingenuo se da a continuación: – 

/* Program to find LCA of n1 and n2 using one DFS on
   the Tree */
#include<bits/stdc++.h>
using namespace std;
 
// Maximum number of nodes is 100000 and nodes are
// numbered from 1 to 100000
#define MAXN 100001
 
vector < int > tree[MAXN];
int path[3][MAXN]; // storing root to node path
 
// storing the path from root to node
void dfs(int cur, int prev, int pathNumber, int ptr,
                             int node, bool &flag)
{
    for (int i=0; i<tree[cur].size(); i++)
    {
        if (tree[cur][i] != prev and !flag)
        {
            // pushing current node into the path
            path[pathNumber][ptr] = tree[cur][i];
            if (tree[cur][i] == node)
            {
                // node found
                flag = true;
 
                // terminating the path
                path[pathNumber][ptr+1] = -1;
                return;
            }
            dfs(tree[cur][i], cur, pathNumber, ptr+1,
                                        node, flag);
        }
    }
}
 
// This Function compares the path from root to 'a' & root
// to 'b' and returns LCA of a and b. Time Complexity : O(n)
int LCA(int a, int b)
{
    // trivial case
    if (a == b)
        return a;
 
    // setting root to be first element in path
    path[1][0] = path[2][0] = 1;
 
    // calculating path from root to a
    bool flag = false;
    dfs(1, 0, 1, 1, a, flag);
 
    // calculating path from root to b
    flag = false;
    dfs(1, 0, 2, 1, b, flag);
 
    // runs till path 1 & path 2 matches
    int i = 0;
    while (path[1][i] == path[2][i])
        i++;
 
    // returns the last matching node in the paths
    return path[1][i-1];
}
 
void addEdge(int a,int b)
{
    tree[a].push_back(b);
    tree[b].push_back(a);
}
 
// Driver code
int main()
{
    int n = 8; // Number of nodes
    addEdge(1,2);
    addEdge(1,3);
    addEdge(2,4);
    addEdge(2,5);
    addEdge(2,6);
    addEdge(3,7);
    addEdge(3,8);
 
    cout << "LCA(4, 7) = " << LCA(4,7) << endl;
    cout << "LCA(4, 6) = " << LCA(4,6) << endl;
    return 0;
}

/* Program to find LCA of n1 and n2 using one DFS on
the Tree */
 
import java.util.*;
 
class GFG
{
 
    // Maximum number of nodes is 100000 and nodes are
    // numbered from 1 to 100000
    static final int MAXN = 100001;
 
    static Vector<Integer>[] tree = new Vector[MAXN];
    static int[][] path = new int[3][MAXN]; // storing root to node path
    static boolean flag;
 
    // storing the path from root to node
    static void dfs(int cur, int prev, int pathNumber, int ptr, int node)
    {
        for (int i = 0; i < tree[cur].size(); i++)
        {
            if (tree[cur].get(i) != prev && !flag)
            {
                // pushing current node into the path
                path[pathNumber][ptr] = tree[cur].get(i);
                if (tree[cur].get(i) == node)
                {
                    // node found
                    flag = true;
 
                    // terminating the path
                    path[pathNumber][ptr + 1] = -1;
                    return;
                }
                dfs(tree[cur].get(i), cur, pathNumber, ptr + 1, node);
            }
        }
    }
 
    // This Function compares the path from root to 'a' & root
    // to 'b' and returns LCA of a and b. Time Complexity : O(n)
    static int LCA(int a, int b)
    {
        // trivial case
        if (a == b)
            return a;
 
        // setting root to be first element in path
        path[1][0] = path[2][0] = 1;
 
        // calculating path from root to a
        flag = false;
        dfs(1, 0, 1, 1, a);
 
        // calculating path from root to b
        flag = false;
        dfs(1, 0, 2, 1, b);
 
        // runs till path 1 & path 2 matches
        int i = 0;
        while (i < MAXN && path[1][i] == path[2][i])
            i++;
 
        // returns the last matching node in the paths
        return path[1][i - 1];
    }
 
    static void addEdge(int a, int b)
    {
        tree[a].add(b);
        tree[b].add(a);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        for (int i = 0; i < MAXN; i++)
            tree[i] = new Vector<Integer>();
 
        // Number of nodes
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(2, 6);
        addEdge(3, 7);
        addEdge(3, 8);
 
        System.out.print("LCA(4, 7) = " + LCA(4, 7) + "\n");
        System.out.print("LCA(4, 6) = " + LCA(4, 6) + "\n");
    }
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find LCA of n1 and
# n2 using one DFS on the Tree
 
# Maximum number of nodes is 100000 and
# nodes are numbered from 1 to 100000
MAXN = 100001
 
tree = [0] * MAXN
for i in range(MAXN):
    tree[i] = []
 
# Storing root to node path
path = [0] * 3
for i in range(3):
    path[i] = [0] * MAXN
 
flag = False
 
# Storing the path from root to node
def dfs(cur: int, prev: int, pathNumber: int,
        ptr: int, node: int) -> None:
             
    global tree, path, flag
 
    for i in range(len(tree[cur])):
        if (tree[cur][i] != prev and not flag):
 
            # Pushing current node into the path
            path[pathNumber][ptr] = tree[cur][i]
             
            if (tree[cur][i] == node):
 
                # Node found
                flag = True
 
                # Terminating the path
                path[pathNumber][ptr + 1] = -1
                return
 
            dfs(tree[cur][i], cur, pathNumber,
                ptr + 1, node)
 
# This Function compares the path from root
# to 'a' & root to 'b' and returns LCA of
# a and b. Time Complexity : O(n)
def LCA(a: int, b: int) -> int:
     
    global flag
     
    # Trivial case
    if (a == b):
        return a
 
    # Setting root to be first element
    # in path
    path[1][0] = path[2][0] = 1
 
    # Calculating path from root to a
    flag = False
    dfs(1, 0, 1, 1, a)
 
    # Calculating path from root to b
    flag = False
    dfs(1, 0, 2, 1, b)
 
    # Runs till path 1 & path 2 matches
    i = 0
    while (path[1][i] == path[2][i]):
        i += 1
 
    # Returns the last matching
    # node in the paths
    return path[1][i - 1]
 
def addEdge(a: int, b: int) -> None:
 
    tree[a].append(b)
    tree[b].append(a)
 
# Driver code
if __name__ == "__main__":
 
    n = 8
     
    # Number of nodes
    addEdge(1, 2)
    addEdge(1, 3)
    addEdge(2, 4)
    addEdge(2, 5)
    addEdge(2, 6)
    addEdge(3, 7)
    addEdge(3, 8)
 
    print("LCA(4, 7) = {}".format(LCA(4, 7)))
    print("LCA(4, 6) = {}".format(LCA(4, 6)))
 
# This code is contributed by sanjeev2552

/* C# Program to find LCA of n1 and n2 using one DFS on
the Tree */
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Maximum number of nodes is 100000 and nodes are
    // numbered from 1 to 100000
    static readonly int MAXN = 100001;
 
    static List<int>[] tree = new List<int>[MAXN];
    static int[,] path = new int[3, MAXN]; // storing root to node path
    static bool flag;
 
    // storing the path from root to node
    static void dfs(int cur, int prev, int pathNumber, int ptr, int node)
    {
        for (int i = 0; i < tree[cur].Count; i++)
        {
            if (tree[cur][i] != prev && !flag)
            {
                // pushing current node into the path
                path[pathNumber,ptr] = tree[cur][i];
                if (tree[cur][i] == node)
                {
                    // node found
                    flag = true;
 
                    // terminating the path
                    path[pathNumber, ptr + 1] = -1;
                    return;
                }
                dfs(tree[cur][i], cur, pathNumber, ptr + 1, node);
            }
        }
    }
 
    // This Function compares the path from root to 'a' & root
    // to 'b' and returns LCA of a and b. Time Complexity : O(n)
    static int LCA(int a, int b)
    {
        // trivial case
        if (a == b)
            return a;
 
        // setting root to be first element in path
        path[1, 0] = path[2, 0] = 1;
 
        // calculating path from root to a
        flag = false;
        dfs(1, 0, 1, 1, a);
 
        // calculating path from root to b
        flag = false;
        dfs(1, 0, 2, 1, b);
 
        // runs till path 1 & path 2 matches
        int i = 0;
        while (i < MAXN && path[1, i] == path[2, i])
            i++;
 
        // returns the last matching node in the paths
        return path[1, i - 1];
    }
 
    static void addEdge(int a, int b)
    {
        tree[a].Add(b);
        tree[b].Add(a);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        for (int i = 0; i < MAXN; i++)
            tree[i] = new List<int>();
 
        // Number of nodes
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(2, 6);
        addEdge(3, 7);
        addEdge(3, 8);
 
        Console.Write("LCA(4, 7) = " + LCA(4, 7) + "\n");
        Console.Write("LCA(4, 6) = " + LCA(4, 6) + "\n");
    }
}
 
// This code is contributed by Rajput-Ji

<script>
/* Program to find LCA of n1 and n2 using one DFS on
the Tree */
 
// Maximum number of nodes is 100000 and nodes are
    // numbered from 1 to 100000
let MAXN = 100001;
 
let tree = new Array(MAXN);
 
let path = new Array(3);
 
for(let i = 0; i < 3; i++)
{
    path[i] = new Array(MAXN);
    for(let j = 0; j < MAXN; j++)
    {
        path[i][j] = 0;
    }
}
 
let flag;
 
/// storing the path from root to node
function dfs(cur,prev,pathNumber,ptr,node)
{
    for (let i = 0; i < tree[cur].length; i++)
        {
            if (tree[cur][i] != prev && !flag)
            {
                // pushing current node into the path
                path[pathNumber][ptr] = tree[cur][i];
                if (tree[cur][i] == node)
                {
                    // node found
                    flag = true;
  
                    // terminating the path
                    path[pathNumber][ptr + 1] = -1;
                    return;
                }
                dfs(tree[cur][i], cur, pathNumber, ptr + 1, node);
            }
        }
}
 
// This Function compares the path from root to 'a' & root
    // to 'b' and returns LCA of a and b. Time Complexity : O(n)
function LCA(a,b)
{
    // trivial case
        if (a == b)
            return a;
  
        // setting root to be first element in path
        path[1][0] = path[2][0] = 1;
  
        // calculating path from root to a
        flag = false;
        dfs(1, 0, 1, 1, a);
  
        // calculating path from root to b
        flag = false;
        dfs(1, 0, 2, 1, b);
  
        // runs till path 1 & path 2 matches
        let i = 0;
        while (i < MAXN && path[1][i] == path[2][i])
            i++;
  
        // returns the last matching node in the paths
        return path[1][i - 1];
}
 
function addEdge(a,b)
{
    tree[a].push(b);
    tree[b].push(a);
}
 
// Driver code
for (let i = 0; i < MAXN; i++)
    tree[i] = [];
 
// Number of nodes
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(2, 6);
addEdge(3, 7);
addEdge(3, 8);
 
document.write("LCA(4, 7) = " + LCA(4, 7) + "<br>");
document.write("LCA(4, 6) = " + LCA(4, 6) + "<br>");
 
// This code is contributed by rag2127
</script>

LCA(4, 7) = 1
LCA(4, 6) = 2

Enfoque de array dispersa (preprocesamiento O(nlogn), O(log n) – consulta) 

Cálculo previo:

Aquí almacenamos el padre 2^i para cada Node, donde 0 <= i < NIVEL, aquí «NIVEL» es un número entero constante que indica el número máximo posible de ancestro 2^i. 

Por lo tanto, asumimos el peor de los casos para ver cuál es el valor de la constante NIVEL. En nuestro peor caso, cada Node en nuestro árbol tendrá como máximo 1 padre y 1 hijo o podemos decir que simplemente se reduce a una lista enlazada. 

Entonces, en este caso LEVEL = ceil ( log(number of nodes) ). 

También calculamos previamente la altura de cada Node usando un dfs en tiempo O(n). 

int n             // number of nodes
int parent[MAXN][LEVEL] // all initialized to -1 

parent[node][0] : contains the 2^0th(first) 
parent of all the nodes pre-computed using DFS

// Sparse matrix Approach
for node -> 1 to n :        
  for i-> 1 to LEVEL :
    if ( parent[node][i-1] != -1 ) :
      parent[node][i]  =  
         parent[ parent[node][i-1] ][i-1]

Ahora, como vemos, el código de programación dinámica anterior ejecuta dos bucles anidados que se ejecutan en su rango completo respectivamente. 
Por lo tanto, se puede inferir fácilmente que su Complejidad de Tiempo asintótica es O(número de Nodes * NIVEL) ~ O(n*NIVEL) ~ O(nlogn).

Devolver ACV(u,v): 

1. El primer paso es llevar ambos Nodes a la misma altura. Como ya hemos calculado previamente las alturas para cada Node. Primero calculamos la diferencia en las alturas de u y v (digamos v >=u). Ahora necesitamos el Node ‘v’ para saltar h Nodes arriba. Esto se puede hacer fácilmente en tiempo O(log h) (donde h es la diferencia en las alturas de u y v) ya que hemos almacenado el padre 2^i para cada Node. Este proceso es exactamente igual que calcular x^y en tiempo O(log y). (Ver el código para una mejor comprensión).
2. Ahora los Nodes u y v están a la misma altura. Por lo tanto, ahora, una vez más, usaremos la estrategia de salto 2^i para llegar al primer padre común de u y v. 

Pseudo-code:
For i->  LEVEL to 0 :
      If parent[u][i] != parent[v][i] :
           u = parent[u][i]
           v = parent[v][i]

La implementación del algoritmo anterior se da a continuación: 

// Sparse Matrix DP approach to find LCA of two nodes
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define level 18
 
vector <int> tree[MAXN];
int depth[MAXN];
int parent[MAXN][level];
 
// pre-compute the depth for each node and their
// first parent(2^0th parent)
// time complexity : O(n)
void dfs(int cur, int prev)
{
    depth[cur] = depth[prev] + 1;
    parent[cur][0] = prev;
    for (int i=0; i<tree[cur].size(); i++)
    {
        if (tree[cur][i] != prev)
            dfs(tree[cur][i], cur);
    }
}
 
// Dynamic Programming Sparse Matrix Approach
// populating 2^i parent for each node
// Time complexity : O(nlogn)
void precomputeSparseMatrix(int n)
{
    for (int i=1; i<level; i++)
    {
        for (int node = 1; node <= n; node++)
        {
            if (parent[node][i-1] != -1)
                parent[node][i] =
                    parent[parent[node][i-1]][i-1];
        }
    }
}
 
// Returning the LCA of u and v
// Time complexity : O(log n)
int lca(int u, int v)
{
    if (depth[v] < depth[u])
        swap(u, v);
 
    int diff = depth[v] - depth[u];
 
    // Step 1 of the pseudocode
    for (int i=0; i<level; i++)
        if ((diff>>i)&1)
            v = parent[v][i];
 
    // now depth[u] == depth[v]
    if (u == v)
        return u;
 
    // Step 2 of the pseudocode
    for (int i=level-1; i>=0; i--)
        if (parent[u][i] != parent[v][i])
        {
            u = parent[u][i];
            v = parent[v][i];
        }
 
    return parent[u][0];
}
 
void addEdge(int u,int v)
{
    tree[u].push_back(v);
    tree[v].push_back(u);
}
 
// driver function
int main()
{
    memset(parent,-1,sizeof(parent));
    int n = 8;
    addEdge(1,2);
    addEdge(1,3);
    addEdge(2,4);
    addEdge(2,5);
    addEdge(2,6);
    addEdge(3,7);
    addEdge(3,8);
    depth[0] = 0;
 
    // running dfs and precalculating depth
    // of each node.
    dfs(1,0);
 
    // Precomputing the 2^i th ancestor for every node
    precomputeSparseMatrix(n);
 
    // calling the LCA function
    cout << "LCA(4, 7) = " << lca(4,7) << endl;
    cout << "LCA(4, 6) = " << lca(4,6) << endl;
    return 0;
}

// Sparse Matrix DP approach to find LCA of two nodes
import java.util.*;
 
class GFG
{
    static final int MAXN = 100000;
    static final int level = 18;
   
      @SuppressWarnings("unchecked")
    static Vector<Integer>[] tree = new Vector[MAXN];
    static int[] depth = new int[MAXN];
    static int[][] parent = new int[MAXN][level];
 
    // pre-compute the depth for each node and their
    // first parent(2^0th parent)
    // time complexity : O(n)
    static void dfs(int cur, int prev)
    {
        depth[cur] = depth[prev] + 1;
        parent[cur][0] = prev;
        for (int i = 0; i < tree[cur].size(); i++)
        {
            if (tree[cur].get(i) != prev)
                dfs(tree[cur].get(i), cur);
        }
    }
 
    // Dynamic Programming Sparse Matrix Approach
    // populating 2^i parent for each node
    // Time complexity : O(nlogn)
    static void precomputeSparseMatrix(int n)
    {
        for (int i = 1; i < level; i++)
        {
            for (int node = 1; node <= n; node++)
            {
                if (parent[node][i - 1] != -1)
                    parent[node][i] = parent[parent[node][i - 1]][i - 1];
            }
        }
    }
 
    // Returning the LCA of u and v
    // Time complexity : O(log n)
    static int lca(int u, int v)
    {
        if (depth[v] < depth[u])
        {
            u = u + v;
            v = u - v;
            u = u - v;
        }
 
        int diff = depth[v] - depth[u];
 
        // Step 1 of the pseudocode
        for (int i = 0; i < level; i++)
            if (((diff >> i) & 1) == 1)
                v = parent[v][i];
 
        // now depth[u] == depth[v]
        if (u == v)
            return u;
 
        // Step 2 of the pseudocode
        for (int i = level - 1; i >= 0; i--)
            if (parent[u][i] != parent[v][i])
            {
                u = parent[u][i];
                v = parent[v][i];
            }
 
        return parent[u][0];
    }
 
    static void addEdge(int u, int v)
    {
        tree[u].add(v);
        tree[v].add(u);
    }
 
    static void memset(int value)
    {
        for (int i = 0; i < MAXN; i++)
        {
            for (int j = 0; j < level; j++)
            {
                parent[i][j] = -1;
            }
        }
    }
 
    // driver function
    public static void main(String[] args)
    {
        memset(-1);
        for (int i = 0; i < MAXN; i++)
            tree[i] = new Vector<Integer>();
        int n = 8;
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(2, 6);
        addEdge(3, 7);
        addEdge(3, 8);
        depth[0] = 0;
 
        // running dfs and precalculating depth
        // of each node.
        dfs(1, 0);
 
        // Precomputing the 2^i th ancestor for every node
        precomputeSparseMatrix(n);
 
        // calling the LCA function
        System.out.print("LCA(4, 7) = " + lca(4, 7) + "\n");
        System.out.print("LCA(4, 6) = " + lca(4, 6) + "\n");
    }
}
 
// This code is contributed by 29AjayKumar

// Sparse Matrix DP approach to find LCA of two nodes
using System;
using System.Collections.Generic;
 
class GFG
{
    static readonly int MAXN = 100000;
    static readonly int level = 18;
 
    static List<int>[] tree = new List<int>[MAXN];
    static int[] depth = new int[MAXN];
    static int[,] parent = new int[MAXN, level];
 
    // pre-compute the depth for each node and their
    // first parent(2^0th parent)
    // time complexity : O(n)
    static void dfs(int cur, int prev)
    {
        depth[cur] = depth[prev] + 1;
        parent[cur,0] = prev;
        for (int i = 0; i < tree[cur].Count; i++)
        {
            if (tree[cur][i] != prev)
                dfs(tree[cur][i], cur);
        }
    }
 
    // Dynamic Programming Sparse Matrix Approach
    // populating 2^i parent for each node
    // Time complexity : O(nlogn)
    static void precomputeSparseMatrix(int n)
    {
        for (int i = 1; i < level; i++)
        {
            for (int node = 1; node <= n; node++)
            {
                if (parent[node, i - 1] != -1)
                    parent[node, i] = parent[parent[node, i - 1], i - 1];
            }
        }
    }
 
    // Returning the LCA of u and v
    // Time complexity : O(log n)
    static int lca(int u, int v)
    {
        if (depth[v] < depth[u])
        {
            u = u + v;
            v = u - v;
            u = u - v;
        }
 
        int diff = depth[v] - depth[u];
 
        // Step 1 of the pseudocode
        for (int i = 0; i < level; i++)
            if (((diff >> i) & 1) == 1)
                v = parent[v, i];
 
        // now depth[u] == depth[v]
        if (u == v)
            return u;
 
        // Step 2 of the pseudocode
        for (int i = level - 1; i >= 0; i--)
            if (parent[u, i] != parent[v, i])
            {
                u = parent[u, i];
                v = parent[v, i];
            }
 
        return parent[u, 0];
    }
 
    static void addEdge(int u, int v)
    {
        tree[u].Add(v);
        tree[v].Add(u);
    }
 
    static void memset(int value)
    {
        for (int i = 0; i < MAXN; i++)
        {
            for (int j = 0; j < level; j++)
            {
                parent[i, j] = -1;
            }
        }
    }
 
    // Driver function
    public static void Main(String[] args)
    {
        memset(-1);
        for (int i = 0; i < MAXN; i++)
            tree[i] = new List<int>();
        int n = 8;
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(2, 6);
        addEdge(3, 7);
        addEdge(3, 8);
        depth[0] = 0;
 
        // running dfs and precalculating depth
        // of each node.
        dfs(1, 0);
 
        // Precomputing the 2^i th ancestor for every node
        precomputeSparseMatrix(n);
 
        // calling the LCA function
        Console.Write("LCA(4, 7) = " + lca(4, 7) + "\n");
        Console.Write("LCA(4, 6) = " + lca(4, 6) + "\n");
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Sparse Matrix DP approach to find LCA of two nodes
var MAXN = 100000;
var level = 18;
var tree = Array.from(Array(MAXN), ()=>Array());
var depth = Array(MAXN).fill(0);
var parent = Array.from(Array(MAXN), ()=>Array(level).fill(-1));
// pre-compute the depth for each node and their
// first parent(2^0th parent)
// time complexity : O(n)
function dfs(cur, prev)
{
    depth[cur] = depth[prev] + 1;
    parent[cur][0] = prev;
    for (var i = 0; i < tree[cur].length; i++)
    {
        if (tree[cur][i] != prev)
            dfs(tree[cur][i], cur);
    }
}
// Dynamic Programming Sparse Matrix Approach
// populating 2^i parent for each node
// Time complexity : O(nlogn)
function precomputeSparseMatrix(n)
{
    for (var i = 1; i < level; i++)
    {
        for(var node = 1; node <= n; node++)
        {
            if (parent[node][i - 1] != -1)
                parent[node][i] = parent[parent[node][i - 1]][i - 1];
        }
    }
}
// Returning the LCA of u and v
// Time complexity : O(log n)
function lca(u, v)
{
    if (depth[v] < depth[u])
    {
        u = u + v;
        v = u - v;
        u = u - v;
    }
    var diff = depth[v] - depth[u];
    // Step 1 of the pseudocode
    for (var i = 0; i < level; i++)
        if (((diff >> i) & 1) == 1)
            v = parent[v][i];
    // now depth[u] == depth[v]
    if (u == v)
        return u;
    // Step 2 of the pseudocode
    for (var i = level - 1; i >= 0; i--)
        if (parent[u][i] != parent[v][i])
        {
            u = parent[u][i];
            v = parent[v][i];
        }
    return parent[u][0];
}
function addEdge(u, v)
{
    tree[u].push(v);
    tree[v].push(u);
}
function memset(value)
{
    for (var i = 0; i < MAXN; i++)
    {
        for (var j = 0; j < level; j++)
        {
            parent[i][j] = -1;
        }
    }
}
// Driver function
memset(-1);
var n = 8;
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(2, 6);
addEdge(3, 7);
addEdge(3, 8);
depth[0] = 0;
// running dfs and precalculating depth
// of each node.
dfs(1, 0);
// Precomputing the 2^i th ancestor for every node
precomputeSparseMatrix(n);
// calling the LCA function
document.write("LCA(4, 7) = " + lca(4, 7) + "<br>");
document.write("LCA(4, 6) = " + lca(4, 6) + "<br>");
 
 
</script>

LCA(4, 7) = 1
LCA(4, 6) = 2

Complejidad del tiempo: 

La complejidad de tiempo para responder a una sola consulta de LCA será O (logn), pero la complejidad de tiempo general está dominada por el cálculo previo de los antecesores 2^ith ( 0<=i<=level ) para cada Node. Por lo tanto, la Complejidad de Tiempo asintótica general será O(n*logn) y la Complejidad de Espacio será O(nlogn), para almacenar los datos sobre los ancestros de cada Node.

Este artículo es una contribución de Nitish Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.