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

Table of Contents

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.

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)).

Related Posts

  • Rotate matrix by 90 degrees in java
    20 May

    Rotate Matrix by 90 degrees in java

    Table of ContentsClockwise or Right Rotate a MatrixAnti-Clockwise or Left Rotate a MatrixHow to Rotate Matrix K Times? In this article, we will look into another interesting problem related to 2D Arrays. Given a Matrix of N X N Dimension we have to Rotate matrix by 90 degrees. We will perform Rotation both Clockwise i.e. […]

  • Data structures in java
    16 April

    Data Structures in java

    Table of ContentsArray Declare and initialize array in javaAdvantages of arrayDisadvantages of array ExampleArray practice programsStackStack implementation using ArrayStack implementation using LinkedListImplementationPractice ProgramsQueueQueue implementation using arrayQueue implementation using LinkedListImplementationLinkedListImplementationLinkedList Practice ProgramsBinary treeImplementationBinary tree practice programsBinary Search treeImplementationBinary search tree Practice programsTrieImplementationHeapImplementationGraphImplementation Inbuild data structures in javaStringHashMapLinkedHashMapArrayListLinkedListHashSet In this post, we will see about various data […]

  • 29 November

    Top 100+ Java coding interview questions

    Table of ContentsStringQuestion 1 : How to reverse a String in java? Can you write a program without using any java inbuilt methods?Question 2 : Write a java program to check if two Strings are anagram in java?Question 3 : Write a program to check if String has all unique characters in java?Question 4 : […]

  • 18 April

    Minimum Number of Jumps to reach last Index

    Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to find Minimum Number of Jumps to reach last Index. Problem Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a […]

  • 20 February

    Inorder Successor in a Binary Search Tree

    Table of ContentsProblemSolutionAPPROACH – I :Approach – II:(i) If the target node has a right child :(ii) If the target node does not have a right child :Time Complexity Discussion If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to […]

  • 03 February

    Largest Rectangular Area in a Histogram

    Table of ContentsProblemSolutionAPPROACH – IAPPROACH – II (RECURSIVE):Approach – III (ITERATIVE) : 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 largest rectangular area in a Histogram. Problem Given an Integer representing number of bars in a […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.