Lowest Common Ancestor (LCA) Problem | Source Code

Key Takeaways

[Music] hello and welcome my name is William today I want to take some time we look at some source code on how to find the lowest common ancestor of two nodes in a tree this video implements the concepts in the previous video where we looked at how to construct an Euler tour around a tree and query the lowest common ancestor if you haven't already watched the explanation video make sure you go and give that a listen and come back all the source code you see today can be found on github at github.com slash will use a slash algorithms alright here we are on the source code for the lowest common ancestor written in Java let's begin by going over an example of how this class is intended to be used in the main method I give three examples of how to do the lowest common ancestor queries the first thing we need to do is actually build a rooted tree in this example I'm reusing the first tree from the slides in the previous video after we've created the tree you can pass the tree into the lowest common ancestor Euler tour constructor at the moment each instance of this class is only meant to handle one tree so if you want to do lowest common ancestor queries on multiple trees you need multiple solvers after the solver is created you can use it to do lowest common ancestor queries in the following example I do three queries to find the LCA of 13 and 14 the LCA of 9 and 11 and the LCA of 12 and 12 let's scroll down to the implementation and take a closer look the first class I want to take a look at is the tree node class you'll notice that this class is mostly the same as before except that it has a new variable n which tracks the number of nodes in the subtree of this tree node including the node itself the tree node also has an index and a list of children most of the methods in this class are accessor methods the only thing when you take a look at are some of the minor changes I made to the build tree method since the routing tree video in the build tree method you'll notice that I'm now counting the number of nodes in the subtree of the current node for our purposes this effectively serves as a nice way to know how many nodes there are in the tree from the root node moving on I want to talk about some of the instance variables in this class the first is and the number of nodes in the tree which is followed by the tour index variable which tracks the index of where we are in the order in tour as we traverse the tree the node depth and the node order arrays are populated during the order in tour they serve to track the depth of each node and a pointer to each node for each index position in the Euler in tour the last map helps keep track of the last occurrence of a node in the ordinary tour and finally is the mint sparse table class to do range minimum queries when creating an instance of the LCA solver you need to provide the root node of the tree you want to do lowest common ancestor queries for from the root node assigned n to be the number of nodes in the tree and call the set up method the setup function is responsible for allocating memory and constructing the order in tour begin by allocating memory for our three arrays node order no depth and last then do a depth first search on the tree to construct the ordering tour after this create a sparse table use the node depth array which was populated during the euler int or the depth-first search method is the one that actually performs the other int or as parameters it tracks the current node and the node depth when the current node becomes null we know that we have reached our base case and can return otherwise visit the current node iterate over all its children recursively the inner visit function call ensures that after visiting a subtree that we revisit the current node this is essential to get the desired or there in tour effect and to traverse the tree as expected the visit function itself is responsible for populating the arrays associated with your layering tour in particular this function will update the nodes array to keep track of pointer to the current node and it will also update the depth array to track the current depth and it will also update the inverse mapping to the or their in tour index so a lot of things going on in the visit function next is the LCA method which finds the lowest common ancestor of two nodes with the indices index 1 and index 2 the first thing we want to do is look inside our last map and find the indices in the order in tour associated with index 1 and index 2 from these values we can extract a left and a right endpoint to make sure the left endpoint always appears before the right endpoint take the min and the max of the indices after we know the left and the right endpoints simply do a range minimum query to find the index of the minimum element in the range l2 our we can do this using the sparse table we created in the setup method and lastly return the tree node object for the lowest common ancestor found in the nodes array below is an implementation of a min sparse table but I'm not going to cover that in this video since I have a dedicated video on sparse tables in my da shorter series if you're interested in that I'll make sure to leave a link below guys thank you for watching I hope you learned something please like this video and subscribe for more mathematics [Music]