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.
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
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
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?
- 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.
- 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 |
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)).
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
