chatgpt LCA Lowest Common Ancestor

The Lowest Common Ancestor (LCA) of two nodes in a tree is the deepest node that is a common ancestor to both nodes. In other words, it's the node furthest from the root that is an ancestor of both nodes. The LCA can be found efficiently using techniques such as Dynamic Programming and Binary Lifting.


Here is an example of finding the Lowest Common Ancestor (LCA) in C# using Dynamic Programming:

class Program
{
    static int[] parent;
    static int[,] dp;
    static int[] depth;

    static void Main(string[] args)
    {
        int n = 5;
        parent = new int[] { -1, 0, 0, 1, 2 };
        depth = new int[n];
        dp = new int[n, (int)Math.Log2(n) + 1];

        // Pre-compute depth of each node
        for (int i = 0; i < n; i++)
        {
            if (depth[i] == 0)
                dfs(i);
        }

        // Pre-compute dp table
        for (int i = 0; i < n; i++)
        {
            dp[i, 0] = parent[i];
        }
        for (int j = 1; j <= (int)Math.Log2(n); j++)
        {
            for (int i = 0; i < n; i++)
            {
                if (dp[i, j - 1] != -1)
                {
                    dp[i, j] = dp[dp[i, j - 1], j - 1];
                }
            }
        }

        int u = 3, v = 4;
        Console.WriteLine("LCA of " + u + " and " + v + " is: " + LCA(u, v));
    }

    static int LCA(int u, int v)
    {
        if (depth[u] < depth[v])
        {
            int temp = u;
            u = v;
            v = temp;
        }

        int d = depth[u] - depth[v];
        for (int i = (int)Math.Log2(depth[u]); i >= 0; i--)
        {
            if ((d & (1 << i)) != 0)
                u = dp[u, i];
        }

        if (u == v)
            return u;

        for (int i = (int)Math.Log2(depth[u]); i >= 0; i--)
        {
            if (dp[u, i] != dp[v, i])
            {
                u = dp[u, i];
                v = dp[v, i];
            }
        }

        return parent[u];
    }

    static void dfs(int u)
    {
        for (int v = 0; v < parent.Length; v++)
        {
            if (parent[v] == u)
            {
                depth[v] = depth[u] + 1;
                dfs(v);
            }
        }
    }
}

This example uses a parent array to represent the tree, where parent[i] is the parent of node i. The depth array is used to store the depth of each node, and the dp table is used to store the LCA information. The LCA function takes two nodes as inputs and returns the LCA using Dynamic Programming. The dfs function is used to pre-compute the depth of each node.