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

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see about how to find Lowest Common Ancestor of a K-ary Tree in O(Sqrt(height)).We have already seen how to find LCA of n-ary tree in O(n) complexity.

Problem

Given a K-ary tree and its two nodes. Calculate the Lowest common ancestor of the nodes in the given tree efficiently in O(sqrt(height)).
Lowest Common Ancestor is the node which is the common ancestor for both the nodes which is closest to them or we can say, farthest from root.

INPUT FORMAT :-
In the first line, given n, the number of nodes, following that n-1 lines contains two integers, the first one representing parent, second one is the child.
After that, given two Integers, whose LCA is to be found.

Solution

The naive approach to find out LCA of two nodes would be keeping two pointers (i.e. one one each node) and keep jumping to the immediate parent of both the current nodes and reach to a point where both the pointers meet, that node will be our LCA for sure.

But this would surely take a time of O(height).

But we can definitely achieve the solution more efficiently in O(√(height)) time.
Instead of jumping one node at a time we can skip more number of nodes which are of no use to us and eventually reach to the required spot where both the nodes meet.
Now HOW do we achieve this?

• We divide our tree in different blocks of Sqrt(h) size i.e each block will be having Sqrt(height) height.
• Now if the total height, ‘h’ of the tree is a perfect square then we know total number of blocks will be sqrt(h), and
  What if the height of the tree is not a perfect square? Still the block size will remain sqrt(h) but the number of blocks will vary in range [sqrt(h), sqrt(h)+2] which can be observed mathematically.
• So Now instead of taking jump of one node, we will take jump of sqrt(h) nodes, which will help us achieve the worst time complexity of sqrt(h) size.

How?

• We set the parent and more importantly the block parent for each node in pre processing itself. Whenever we are asked to find the LCA of two nodes and if they belong to different blocks,  we first make their block parents same so that atleast they are in the same block, therefore, to achieve that we make the deeper node jump to its block parent until the blocks of both the nodes are same. Now in the worst case, one node will jump all the blocks, which can be sqrt(h) at max, hence the total time taken in this process would be sqrt(h).
• Now after the blocks of both nodes are same, we jump to their immediate parent until the nodes eventually meet, and that meeting point will be the LCA of given nodes. Now at max one node can jump all the nodes in its block which can be sqrt(h) at max.
• So the total time complexity of the algorithm will be : Sqrt(h) + Sqrt(h)
  = 2*Sqrt(h)
  = O(Sqrt(h))

Algorithm :

• In the first DFS we set the parents, depths and more importantly find the height which helps us to define the size of each block.
• After we find height of the tree, we define the block size of the tree.
• Now once the block size is defined, we can set the block parent of each node in the tree.
  For setting the block parent, we keep two things in mind,
  • (i) if a node and the parent of that node lies in the same Block number, then they have the same block parent, that is, block parent of node = block parent of parent.
  • (ii) if a node and the parent of that node lies in different Block numbers, then the block parent of node is the actual parent of the node, that is, block parent of node = parent.
• Once the block parent is set we are done with pre processing and remaining is to process the query.

How to process the query?

1. If the nodes are in the different blocks, then make the deeper node jump to its block parent until they are in the same block number.
2. If the block number of both the nodes are same, then make the deeper node jump to its immediate parent until they actually meet. This node where the two nodes actually meet is the LCA.

package org.arpit.java2blog;

import java.util.ArrayList;
import java.util.Scanner;

public class LCAsqrtdecomp {

    static ArrayList<Integer>[] tree;
    static int[] parents;
    static int[] depths;
    static int[] blockParents;
    static int height;
    static int blockSize;

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);

        int nodes = scn.nextInt();
        int edges = nodes - 1;

        tree = new ArrayList[nodes + 1];

        // parents arr to store the parent of the ith node.
        parents = new int[nodes + 1];

        // blockParents arr to store the block parent of the ith node.
        blockParents = new int[nodes + 1];

        // depths to store the height of the current node
        depths = new int[nodes + 1];
        height = -1;

        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }

        for (int i = 0; i < edges; i++) {
            int parent = scn.nextInt();
            int child = scn.nextInt();

            // at the index of the parent node, we are adding its child
            tree[parent].add(child);
        }

        /* this dfs is to set the parents, depths, 
           and mainly to find the height of the
           tree given so that we can calculate our
           blocksize which will be sqrt(height).
        */
        dfs(1, 0, 0);

        /* incrementing the height by one, because the 
        height we calculated was started considering the
        root node at 0th level, but certainly root node also
        contributes to the total height of the tree.
         */
        blockSize = (int) Math.sqrt(++height);

        /* this is again a sort of DFS in which we are 
         setting the block parent for every node. we could 
         not do it in the previous dfs as before we didnt have
         our height precalculated for finding the blocksize
         */
        setBP(1);

        System.out.println("Output: "+getLCA(scn.nextInt(), scn.nextInt()));

    }

    public static void dfs(int node, int parent, int currDepth) {
        // setting parent and depth of the current node.
        parents[node] = parent;
        depths[node] = currDepth;
        // always updating Max Height as we move down 
        // in tree using preorder traversal. 
        height = Math.max(height, currDepth);

        for (int child : tree[node]) {
            // recurring for all the child nodes for which the 
            // current node will act as the parent .
            dfs(child, node, currDepth + 1);
        }

    }

    public static void setBP(int node) {

        int parent = parents[node];

        /* finding the block number of the current node and 
         its parent by diving the depth by blocksize.
        */
        int nodeBlock = depths[node] / blockSize;
        int parentBlock = depths[parent] / blockSize;

        /* if they both current node and the previous node lie in 
         the same block, then lie in the same block, then this means 
         that the block size of both nodes must be the same node, and 
         as we have already calculated the block parent of parent, so 
         the Block parent of current node will be the block parent of 
         the parent of current node.
         */

        if (nodeBlock == parentBlock) {
            blockParents[node] = blockParents[parent];
        } else {
            /* if the blocks of current node and its parent are  
             different then this means that the immediate parent  
             of the current node lies in the just the previous 
             block and hence the actual  parent of the current
                          node is also its block parent.
             */
            blockParents[node] = parents[node];
        }

        for (int child : tree[node]) {
            /* recurring for the child nodes, we do not really 
               need to send the parent in the call, a we have 
               already calculated  and stored them in the previous 
                           dfs.
            */
            setBP(child);
        }

    }

    public static int getLCA(int node1, int node2) {

        /* this is the part where all of our complexity reduction 
         * occurs, instead of jumping one be one, we directly 
         * take jumps of sqrt(height) size. if the block parent 
         * of both the nodes are different, then we jump to the 
         * block parent of the DEEPER node. we keep on doing the 
         * same until the block parent of both the nodes are equal.
         */
        while (blockParents[node1] != blockParents[node2]) {
            /*
             * this check takes care that we make the deeper node 
             * jump to its block parent, if this check was not 
             * there, there might be a case where both nodes
             * eventually reach to the block parent of the root node
             */
            if (depths[node1] > depths[node2]) {
                node1 = blockParents[node1];
            } else {
                node2 = blockParents[node2];
            }
        }

        /*
         * once the blocks of both the nodes are same, this 
         * means that the LCA of both the nodes must lie in 
         * the same block, therefore now we keep jumping to the
         * immediate parent of the nodes until the nodes actually 
         * meet, the point where they meet will be our LCA
         */
        while (node1 != node2) {

            if (depths[node1] > depths[node2]) {
                node1 = parents[node1];
            } else {
                node2 = parents[node2];
            }
        }

        // finally return the LCA of both the nodes
        return node1;
    }

}   

That’s all about how to find Lowest Common Ancestor(LCA) of a K-ary Tree in O(Sqrt(height)).