1
00:00:00,170 --> 00:00:02,030
Hey there and welcome back.

2
00:00:02,030 --> 00:00:05,990
Let's do this question which is called path sum number two.

3
00:00:05,990 --> 00:00:15,020
And the question reads given the root of a binary tree and an integer target sum, return all root to

4
00:00:15,020 --> 00:00:21,380
leaf paths where the sum of the node values in the path equals target sum.

5
00:00:21,710 --> 00:00:27,650
Each path should be returned as a list of the node values, not node.

6
00:00:27,650 --> 00:00:28,640
References.

7
00:00:28,970 --> 00:00:34,250
A root to leaf path is a path starting from the root and ending at any leaf node.

8
00:00:34,580 --> 00:00:37,040
A leaf node is a node with no children.

9
00:00:37,040 --> 00:00:39,020
Okay, so that's the question at hand.

10
00:00:39,020 --> 00:00:40,910
And we are given an example.

11
00:00:40,910 --> 00:00:46,070
So if this is the binary tree which is given to us and if the target sum is 20.

12
00:00:46,100 --> 00:00:52,910
Notice that if you go from the root till this leaf over here you have seven, three, five and five.

13
00:00:52,910 --> 00:00:57,230
And if you add these values it totals up to 20.

14
00:00:57,230 --> 00:01:01,610
And that's how we get this element over here okay 7355.

15
00:01:01,610 --> 00:01:02,960
And it's a list.

16
00:01:02,960 --> 00:01:07,640
And this path over here also which starts from the root and goes up to this leaf.

17
00:01:07,640 --> 00:01:12,290
If you take that into consideration notice that the values add up to 20.

18
00:01:12,290 --> 00:01:16,250
So seven plus six plus four plus three adds up to 20.

19
00:01:16,250 --> 00:01:18,740
And that's why we have this element over here.

20
00:01:18,740 --> 00:01:24,410
And the required output is a list of these list elements.

21
00:01:24,410 --> 00:01:26,270
So that's the question at hand.

22
00:01:26,270 --> 00:01:33,980
And again remember the question says return all root to leaf paths where the sum of the node values

23
00:01:33,980 --> 00:01:35,840
in the path equals target sum.

24
00:01:35,840 --> 00:01:43,490
Now because it's asking to return all the possible root to leaf paths, it's a strong indication that

25
00:01:43,490 --> 00:01:46,460
we can use backtracking to solve this question.

26
00:01:46,460 --> 00:01:50,750
And again, we have discussed this previously when we discussed backtracking in detail.

27
00:01:50,750 --> 00:01:57,290
So whenever you have to explore all the possible solutions, typically we will solve these type of questions

28
00:01:57,290 --> 00:01:58,580
with backtracking.

29
00:01:58,760 --> 00:02:00,920
So we have understood the question.

30
00:02:00,920 --> 00:02:07,790
Now always remember it's very important to ask clarifying questions once you are presented with a coding

31
00:02:07,790 --> 00:02:08,630
interview question.

32
00:02:08,630 --> 00:02:17,150
So a question which is very important to ask over here is whether the nodes can have only positive values

33
00:02:17,150 --> 00:02:21,200
or whether it's possible that the values of the nodes are negative as well.

34
00:02:21,200 --> 00:02:28,610
And let's say the interviewer replies that the nodes can have positive as well as negative values.

35
00:02:28,610 --> 00:02:35,810
Now this is very important because if all the values were positive and let's say we go down a branch

36
00:02:35,810 --> 00:02:42,320
and we reach a level where the sum of the elements in the array that we are building as we go down this

37
00:02:42,320 --> 00:02:44,450
path is greater than the target sum.

38
00:02:44,450 --> 00:02:45,920
We could have stopped, right?

39
00:02:45,920 --> 00:02:49,760
Because by going further down we would just keep increasing the value.

40
00:02:49,760 --> 00:02:54,140
But because the values can be positive as well as negative.

41
00:02:54,140 --> 00:02:55,790
So we can't stop.

42
00:02:55,790 --> 00:02:58,730
Like for example, let's say the target sum was 20.

43
00:02:58,730 --> 00:03:00,350
And over here we have seven three.

44
00:03:00,350 --> 00:03:01,850
And let's say we have 15 over here.

45
00:03:01,850 --> 00:03:07,310
So when you come over here, by the time you reach over here the sum would be 25, right.

46
00:03:07,310 --> 00:03:09,410
And 25 is greater than 20.

47
00:03:09,410 --> 00:03:14,210
And if we knew that all the values were positive, we could stop at that point.

48
00:03:14,210 --> 00:03:20,420
But over here, because values can be positive as well as negative, we can't stop at that point.

49
00:03:20,420 --> 00:03:24,020
Because what if the value over here is negative five?

50
00:03:24,020 --> 00:03:28,220
In that case, when you take all these values you will get 20, right?

51
00:03:28,220 --> 00:03:33,230
So again this is a very important question that you should be asking in this question.

52
00:03:33,230 --> 00:03:38,360
In the next video, let's briefly discuss the method that we can use to solve this question.