Hey there and welcome back.
Let's do this question which is called path sum number two.
And the question reads given the root of a binary tree and an integer target sum, return all root to
leaf paths where the sum of the node values in the path equals target sum.
Each path should be returned as a list of the node values, not node.
References.
A root to leaf path is a path starting from the root and ending at any leaf node.
A leaf node is a node with no children.
Okay, so that's the question at hand.
And we are given an example.
So if this is the binary tree which is given to us and if the target sum is 20.
Notice that if you go from the root till this leaf over here you have seven, three, five and five.
And if you add these values it totals up to 20.
And that's how we get this element over here okay 7355.
And it's a list.
And this path over here also which starts from the root and goes up to this leaf.
If you take that into consideration notice that the values add up to 20.
So seven plus six plus four plus three adds up to 20.
And that's why we have this element over here.
And the required output is a list of these list elements.
So that's the question at hand.
And again remember the question says return all root to leaf paths where the sum of the node values
in the path equals target sum.
Now because it's asking to return all the possible root to leaf paths, it's a strong indication that
we can use backtracking to solve this question.
And again, we have discussed this previously when we discussed backtracking in detail.
So whenever you have to explore all the possible solutions, typically we will solve these type of questions
with backtracking.
So we have understood the question.
Now always remember it's very important to ask clarifying questions once you are presented with a coding
interview question.
So a question which is very important to ask over here is whether the nodes can have only positive values
or whether it's possible that the values of the nodes are negative as well.
And let's say the interviewer replies that the nodes can have positive as well as negative values.
Now this is very important because if all the values were positive and let's say we go down a branch
and we reach a level where the sum of the elements in the array that we are building as we go down this
path is greater than the target sum.
We could have stopped, right?
Because by going further down we would just keep increasing the value.
But because the values can be positive as well as negative.
So we can't stop.
Like for example, let's say the target sum was 20.
And over here we have seven three.
And let's say we have 15 over here.
So when you come over here, by the time you reach over here the sum would be 25, right.
And 25 is greater than 20.
And if we knew that all the values were positive, we could stop at that point.
But over here, because values can be positive as well as negative, we can't stop at that point.
Because what if the value over here is negative five?
In that case, when you take all these values you will get 20, right?
So again this is a very important question that you should be asking in this question.
In the next video, let's briefly discuss the method that we can use to solve this question.