Welcome back.
Let's now implement the code for solving path sum two.
Okay.
So we are given this function over here.
And to this function the root of the binary tree and the target sum is given.
Okay.
And let's now first write the skeleton of the approach that we are going to take.
So we will be having a results array where I will be storing all the root to leaf combinations that
add up to target sum.
Okay.
And then finally we will be returning it over here.
All right.
And we will also be needing a helper function.
And let me just call this function helper itself.
And to this function we will be passing a node.
We can call it root.
And we'll also be passing the remaining sum which we need at a particular instance and the current array.
Now car over here is going to be a combination of elements from the root up to the previous node for
a particular instance.
Okay.
Now inside this function we will be writing the base case as well as the recursive case.
But for now I'm just keeping placeholders over here.
Let's write the details later.
And once we are done with that, we'll have to call the helper function once.
And at that point we'll be passing the root which is given to us, which is this value over here.
And the remaining sum would be the target sum itself.
Because as of now nothing has been added to car, and therefore car is also just going to be an empty
array.
Okay.
So this is the skeleton of the approach that we are going to take.
Now let's go ahead and write the details over here.
Now the base case would be the scenario where the root is equal to null.
And in that case, we will just return.
Okay.
Now this can happen in two ways.
The first way is that if the binary tree itself is empty, and the other case in which this can occur
is once we visit a leaf node, and then if we try to go left or right from there, we would get that
this node over here is equal to null.
Okay.
Now if this is not the case, let's proceed with the recursive case.
Now over here we will have to push the value of this particular node to cur.
So I can say cur dot push root dot val.
Okay.
And we will have to do this even if the remaining sum is negative.
Okay.
And the reason for this is in the question.
It's mentioned that values can have negative values as well.
So let's say at a point, the total value of elements that have been added to the curve is equal to
1 or 2.
And let's say the target sum is equal to 100.
Okay.
Now we can't stop at this point because it could be that the leaf element has a value of minus two.
And in that case 102 minus two would give us 100 okay.
And let's say this is the leaf node.
So that would be a valid case.
So that's why no matter what we will have to push the value of this particular node to occur.
And then we are going to check whether we have arrived at a leaf node where the sum of the values from
the root node up to this particular node is equal to the target sum.
So that's what we are going to check over here.
So for that I'll say if rem sum is equal to root dot val.
Because remember, even though we push this particular value to curb, we have not yet changed REM some,
which is what we got over here.
So that's why we are checking whether rem sum is equal to root dot val.
And that's just a way of checking whether adding this particular value to the current array would result
in a combination whose sum is equal to the target sum.
And if this is true, we would also need to check whether this particular node root is a leaf node.
Okay.
And to check that we will just check whether root dot left is equal to null and root dot right is equal
to null.
Okay.
So if these two things are true that is if rem sum is equal to root dot val.
And if this particular node root is a leaf node, then we have identified a valid root to leaf combination
that adds up to the target sum.
And therefore we would just make a copy of Cur at this particular instance, and we would just push
it to the results array.
So that's what you're doing over here.
And again we have to make a copy because this is a backtracking approach.
And changes to Cur are made in place okay.
And if this is not the case then as we have discussed in the previous video, we will have to explore
going to the left part and to the right part.
So first let's go to the left.
So I will have root dot left over here.
And the remaining sum would have to be updated to rem sum minus root dot val.
Because we added this particular value to curve over here.
And then we'll also have to pass curve to it okay.
And then we'll also have to explore the right path which is helper root dot right.
And then again we have the same rem sum and curve values as we have over here.
So let me just copy and paste it over here.
And that's it.
Now once we are out of this we'll have to do the backtracking step which is curved dot pop okay.
So this is the backtracking step.
And again this is important because probably we would want to go one level up and then visit another
branch in the recursive tree.
So this is how we can solve path sum two.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.