Complete Responsive Online Prevention – Medical – Clinic – Doctor Website Design Free Download Template.
Lowest Common Ancestor
The Lowest Common Ancestor thing sounds a little hard, but the thing is simple and very useful. Several types of problems can be solved with this algorithm. We’ll first look at a bruteforce algorithm for finding the lowest common ancestor, then learn a new data structure called a sparse table to bring the complexity down to the log.
Complete Responsive Online Prevention – Medical – Clinic – Doctor Website Design Free Download Template
First of all we don’t know what LCA or LCA is. See the image below:
In the figure, if k and n move back and forth through the parent of node, they will meet at node i. i is the lowest common ancestor of k,n. ‘a’ and two are common ancestors but i is ‘lowest’ or closest.
Think of the tree as the supervisor or boss in an office. a is the head of office, boss of b and i is a, again boss of c and f is b etc. Then we can easily find the lowest/nearest common boss of two employees using the Least Common Ancestor algorithm.
First we look at a very naive approach that won’t work for very large inputs. Suppose we want to find the LCA of k,n, first taking the parent of k and going up and listing all the ancestors:
If we go from left to right in both lists, the first two nodes that will be common will be LCA! In this example we will first get the common i, so that will be the LCA. ‘a’ is also a common ancestor but not the “lowest”. We can easily implement this algorithm using a visited array or flags. First, I will flag on the index of those who are in the list of k, then I will loop through the list of n and see which node has the flag on.
We can visit at most n nodes to construct each list, so the complexity is O(n).
O(n) complexity is not bad if we only need to derive LCA of one pair of nodes. If we are given m pairs of nodes to find the LCA of each pair then the complexity will be O(m*n). We can solve this in O(m*log(n)) if we want, i.e. each query will run in O(logn). But before that some pre-processing has to be done.
For each node we save the node:
1st parent or 2nd parent
2nd parent or 2^1st parent
4th parent or 2nd parent
8th parent or 2^3rd parent
If there is no K-th parent then we leave –1. As root node has no first parent, first parent will be –1.
Then a 2-dimensional table is created for the above tree as follows:
Then a 2-dimensional table is created for the above tree as follows:
This table is called sparse table. What is the benefit of making this table? Now you can easily find the kth parent of a node. For example, if one needs the 25th parent, first find the highest power of 2 under 25, 2^4=16th parent. Then find the 16th parent (25-16) = 9th parent in the same way! We take advantage of the fact that every number can be expressed as a sum of powers of 2. In this way, in O(logn) complexity, we can find the kth parent of someone, which will be useful to find the LCA later.
Now the question is how to make the table above? Finding the 2^0th parent is easy, by doing a depth-first-search or breathed-first-search on the tree and saving whose parent is in an array. Assume that the array is T . Then for the above tree we get T[0]=-1, T[1]=0,T[6]=5 etc.
Now we will fill the table column-by-column. First we will fill the first column which is actually equal to T array.
Complete Responsive Online Prevention – Medical – Clinic – Doctor Website Design Free Download Template
If the table name is P then fill the first column like this,
for (i = 0; i < N; i++)
P[i][0] = T[i];
Now think 2^4=16th parent of a node is 2^3=8th parent of node 2^3=8th parent. Then the 2^jth parent of a node will be the 2^(j-1)th parent of the 2^(j-1)th parent of the node! Then for any node i:
P[i][j]=P[P[i][j – 1]][j – 1] where P[i][j – 1] is the j-1st parent.
Then I can populate the entire table like this:
for (j = 1; (1 << j) < N; j++)
for (i = 0; i < N; i++)
if (P[i][j – 1] != -1)
P[i][j] = P[P[i][j – 1]][j – 1];
If the value of 2^j is not smaller than N then no new parent is likely to be found, so the loop will run until (1<<j) or 2^j as long as N is smaller.
Now we will calculate LCA of two nodes. We need another additional array L[] which will contain the depth or level of each node. The level of the root node will be 0.
Now we want to find the LCA of the two yellow nodes:
The first task will be to bring them to the same level. Continue subtracting the power of 2 from the level of p and simultaneously raising it using the sparse table until it equals the level of q.
Now the two have reached the same level. Now the task is to drag the two nodes up together until the parents of the two nodes come together:
The code would be like this:
We bring p,q to the point where they both have the same parent. So now the parent of p or q will be LCA.
What would have happened if we had tried to bring nodes 2 and 8 directly to node 1 instead of p,q in the loop? What would happen if the condition P[p][i] != P[q][i] did not exist? It’s your job to figure it out.
Complexity:
Sparse table has n rows, each row has logn columns, pre-processing complexity is O(nlogn).
Complexity per query is O(logn).
Related problems:
1. A weighted tree is given. Given two nodes, we need to find the distance between them. (Spoj QTree)
2. A weighted tree is given. Given two nodes, the value of the highest weighted edge of the path between them must be given. (LOJ A Secret Mission)
Solution 1: Save the distance of each node from the root by running dfs at the beginning. Now if the two nodes are a,b and their common ancestor is L then the solution will be dist(root,a)+dist(root,b)-2*dist(root,L).
Solution 2: Add one more information to the sparse table. For each parent 2^0, 2^1, 2^2 etc. from each node, the value of the highest weight edge of the path between the parent and that node should be saved. I wrote in detail, it is your job to solve it.
Some more problems:
TJU Closest Common Ancestors
UVA Flea Circus
LightOJ LCA Category
Resources:
There are other methods of extracting LCA which can be found here. In addition to these, Tarzan has an offline algorithm that first runs a DFS on all query inputs to extract all pairwise LCAs.
Complete code:
The tree must be saved in the vector g. First call dfs function to fix level, parent and then call lca_init to do preprocessing.
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free
Follow Us
Thank You,
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
FreeWebsiteCreate.net tries to provide HTML, CSS, SCSS, JavaScript, React, Android Studio, Java, PHP, Laravel, Python, Django, C#(C Sharp), and ASP.net-related projects 100% free. We try to make learning easier. Free Website Create always tries to give free projects to new learners. Free projects and source code will help to learn quickly.
They can save time and learn more. In this post, we share a free portfolio project website code with HTML and CSS. This free code portfolio contains a single landing page with a responsive design. In this post, we get a free best carpenter and craftsman service website designed by FreeWebsiteCreate with HTML, CSS, Bootstrap, and JavaScript.