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

Previous
Next

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.

LCA n-ary tree

INPUT :
61
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
4 10
5 11
6 12
7 13
7 14
8 15
9 16
10 17
11 18
11 19
12 20
14 21
14 22
16 23
16 24
17 25
18 26
19 27
20 28
20 29
22 30
22 31
24 32
25 33
25 34
27 35
27 36
29 37
30 38
32 39
32 40
34 41
35 42
35 43
36 44
37 45
37 46
39 47
39 48
39 49
43 50
43 51
46 52
49 53
49 54
51 55
51 56
52 57
53 58
53 59
53 60
53 61
23 61
OUTPUT :
16

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.

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

Previous
Next

Join Our News Letter – Stay Updated

Subscribe to Awesome Java Content.




Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog