LCA of a K-ary Tree in O(Sqrt(height))

ghz 10months ago ⋅ 63 views

To find the Lowest Common Ancestor (LCA) of a K-ary tree in O(sqrt(height)), you can use a method similar to the square root decomposition technique. The basic idea is to decompose the tree into sqrt(height) levels, and then store information about the ancestors of each node at these levels. By doing so, you can reduce the time complexity of finding the LCA to O(sqrt(height)).

Here's how you can implement this:

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    List<TreeNode> children;

    TreeNode(int x) {
        val = x;
        children = new ArrayList<>();
    }
}

public class KaryTreeLCA {

    public TreeNode findLCA(TreeNode root, TreeNode node1, TreeNode node2) {
        // Find the heights of node1 and node2
        int height1 = findHeight(root, node1);
        int height2 = findHeight(root, node2);

        // Adjust node1 and node2 to the same height
        while (height1 > height2) {
            node1 = getParent(node1, root);
            height1--;
        }
        while (height2 > height1) {
            node2 = getParent(node2, root);
            height2--;
        }

        // Move up until the LCA is found
        while (node1 != node2) {
            node1 = getParent(node1, root);
            node2 = getParent(node2, root);
        }

        return node1;
    }

    // Function to find the height of a node in the tree
    private int findHeight(TreeNode root, TreeNode node) {
        if (root == null) {
            return -1;
        }
        if (root == node) {
            return 0;
        }
        for (TreeNode child : root.children) {
            int height = findHeight(child, node);
            if (height >= 0) {
                return height + 1;
            }
        }
        return -1;
    }

    // Function to get the parent of a node in the tree
    private TreeNode getParent(TreeNode node, TreeNode root) {
        if (node == root) {
            return null;
        }
        for (TreeNode child : root.children) {
            if (child == node) {
                return root;
            }
            TreeNode parent = getParent(node, child);
            if (parent != null) {
                return parent;
            }
        }
        return null;
    }
}

In this implementation:

  • The findLCA method takes the root of the tree and two nodes whose LCA needs to be found.
  • First, it finds the heights of both nodes using the findHeight method.
  • Then, it adjusts both nodes to the same height by moving them up to their respective parents until they are at the same level.
  • Finally, it moves both nodes up simultaneously until they reach the LCA.
  • The findHeight method recursively finds the height of a node in the tree.
  • The getParent method recursively finds the parent of a node in the tree.
#algorithm