Hello everyone today we are going to solve another interview problem in C plus plus. And this problem is to find the lowest common ancestor of two. Given bantering notes in a binary tree. So just to illustrate this problem, we look at this example, trade in the main function for this question. We don't care about the order of the numbers. So this tree may not be a battery surgery but just an ordinary binary tree. And for those who aren't so familiar with the concept lowest common ancestor, The lowest common ancestor is first is the common ancestor of two notes. And as the lowest meaning the um if you look at the tree it's near the bottom. So for example we have five and 1 here then it's common, lowest common ancestor would be story. And if we take the example six and 4 we when we are trying to find the lowest common ancestor from each note, we go above many, we go to its parent and its parent of parents to see when they need it. So from four we go up we get to and then we get five and from six we also get five. So five is the common ancestor and it's the first common ancestor. So we consider this as the lowest. Of course three could be another common ancestor but it's not the lowest. Yeah, so I hope you get this idea then we can go ahead to do this question in an interview is very important at first for you to figure out what are the input and output of the the problem or like the solution function. So for this question you are giving a um trained node pointer in C plus plus to the root of the trip which means you can access the trip from the root and then you're giving another trip node pointers um say maybe P and Q. For the output. We're gonna out put another tree node pointer. Um Yeah so let's first write this down as our function signature. Not here. I have um I prefer to have a class solution for this problem. We will see why we why I chose to do this. So let's first have our solution function which is um we have the output tray node pointer. Let me write this down. Okay so clear is it? So um I'm very important thing to clarify here is that we are returning the trainer pointer not the value of the training. We know that it's tree node has a value, integer value but one caveat is that there could be duplicate numbers industry. The returning the integer value may not identify a unique train note. So it's very important to keep in mind that if there are duplicate values industry um whatever we're comparing the notes we have to compare the pointers. Now the integer value and um this part you have to come after I have to confirm with your interviewer whether there will be duplicate values. And another thing we may also want to come consider is that for this input route, could it be representing an empty tree? Um if that's so how what what should we output? So if the route is no pointer that represents an entity tree, there's nothing there so we can return no printer. This would reflect our reflect in our corner case handling for our solution. So without further ado let's first um have a structure to represent this train note. It's very common in the interview that the interviewer asks you to represent or like to write your own train of structure so be sure, you know how to do this here? We have the value and the the left hand, right printer. And then we have a simple constructor taking in just an integer and default the left and right pointers to the to know pointers. So next let's think about how to implement this. Like how to solve this. For example, let's take a look at our example tree. If we have five and one as the input notes, how do we find? It's common ancestor. 1st. We need to of course add the root or like add and a note. If we haven't found a solution we need to explore our Children and all our Children because we don't know where our input notes are um sitting at which um means that we need to do a binary tree, traversal and when we need to do a traverse. So there's only two ways you can do that um as BFFs, breath for search or DFS that's research for now, maybe we can do the DFS which uses Ryker shin um so it's simpler to implement and we don't need to keep a stack to record the note we are looking at so um yes, for DFS since it's a record version every time we're looking at a single note. So let's say We're looking at three, How do we know if three is a lowest common ancestor or not? First to determine if it's a common ancestor, we can um look at first story, it's clearly one of the input notes. No um or then we take a look at its left and right Children. So we asked if in the left trout Or in the left sub tree of three, is there like is the input no tiene que in this branch, if p and q are in this left branch, then we should continue exploring this left branch because the lowest common ancestor would be in this left branch. Similarly for the red bridge, but if the left branch has one of the input nodes and the right branch has one of the input notes, That means our three is low is the common ancestor. So that's a solution and also if three is one of the input and and uh one of its sub tree has and the other input then it means our current three is a solution. So that's the process of determining a common ancestor but how to find a lowest common ancestor, it's simple. We can keep a private member in that solution. Let's keep a train of printer to store our solution cause answer. And when we are traversing our binary tree, if we found a solution, because we are traversing basically from bottom up. So if we find a solution, we assign it to our answer pointer and then return true. So as soon as we find the first solution, we return so it guarantees that it will be the lowest common ancestor. Of course we need to initialize this answer. Um train the pointer, let's um through the constructor of the solution and assign it to a now pointer and in our lowest common entropy function we will use a DFS so we need to have a DFS function. Um Hello and then you know, our lowest common ancestor, we will call this D s s passing in the note he and Q. Because basically the note at the root represent the current note we are looking at and p and Q are just referenced to the two notes we are looking for. So let's look at our dss function as with as I said um every time we are looking at the substrates and we want to know if the input notes are in the substrate so that basically translates to we want to return a bullying type for our DFS to tell that if there exist in the input note. So let's look at the let's implement this DFS. So first, the corner case we have to consider if the route is an is a no printer which means either um, maybe either the tree is empty or we are at the leaf nodes so there's nothing there. Then we return false and we can look at our left and right. Secretary by calling the F S on our left or fled pointer here, the left and right bullying represent if there exists the input notes in our sub tress, of course we need to check whether our roots equals to one of the input. If so it means that our route, you may qualify for the lowest common ancestor or we'll just propagate this result upwards to tell our parents that you have one of the and put here and then let's write the logic for determine whether the route is the lowest common ancestor here. We need three checking conditions if left and right, both um, both true then it means um, one of the input is uh in the last steps where the others in the substrate. So our route is the lowest common ancestor, then we have the left and fruit bullying. So it's one in the left sub tree and the other is the root similar thing for the right. When we found such condition as we said, we store that in the answer and we immediately return to this will guarantee that This is the lowest one and at the end we are only interested in whether we have the input so we return a or veteran ghost three. Any one of them is true which is returned true and this is our the end of our solution. So let's let's move on to the main function. Let's write some task case to check our solution works. So here for this simple tree um I think I'm actually having P to the root left is five and the queue is the current right, which is four? Yeah. Mhm. Okay. So let's run our solution. Let's compile this file and see for here the output should be five because four is the grandchild of our offer. Five. Let's feel good. Um STD Okay. And let's run it. Yeah, so there were thousands five which music works then let's check our corner case for example the road pointer is now in the DFS here we just return false and in the manufacture in we return answer an answer as no point. So it also works for this edge case in an interview. You can also dry read a test case because you may not be able to compare and granite. Let's take a easy example. And let's try running it. Let's say our p. s. three and our Q. Is what? So the answer will be free in our lowest common ancestor function We will um DFS under route three So let's look at the DFS on three. The left will return now because there's nothing there, the right will return to because Q is in in the right secretary and the route bullying will return to because P is three. So in this check condition we will assign the answer 2 3 and return to and I think we skip the part of the F S on what? So let's check If the FS on one hour left is false, right is false. Root bullying is true but we don't certify this, satisfy this condition so our answer is not change. We are not in this cloth but we return true for a while. Yeah, so that's it. The final step will be let's analyze the complexity for one time. In the worst case we're gonna travel the whole tree. For example, you have something like six and 8 as the input, you're going to travel the whole tree. Um in that case our runtime complexity will be all of in for it is the number of nodes industry and then for the storage, the space complexity for this D F s we don't have actual like additional space but we are for the Ryker shin we're using a cost back and the call stack will be the head of the tree. So here the head of the tree is locked in so our runtime complexity will be all of log in but however, if the tree is not balanced, it's screwed. So in the worst case of this complexity is also all of it. Yeah, so this is how we solve these questions. I hope you enjoy it and leave me some feedback If you have any. Thank you so much and see you next time.