1
00:00:00,550 --> 00:00:01,690
Welcome back.

2
00:00:01,690 --> 00:00:05,410
Let's now implement the code for solving path sum two.

3
00:00:05,440 --> 00:00:05,800
Okay.

4
00:00:05,800 --> 00:00:07,480
So we are given this function over here.

5
00:00:07,480 --> 00:00:12,370
And to this function the root of the binary tree and the target sum is given.

6
00:00:12,430 --> 00:00:12,910
Okay.

7
00:00:12,910 --> 00:00:16,660
And let's now first write the skeleton of the approach that we are going to take.

8
00:00:16,660 --> 00:00:23,530
So we will be having a results array where I will be storing all the root to leaf combinations that

9
00:00:23,530 --> 00:00:24,610
add up to target sum.

10
00:00:24,610 --> 00:00:25,030
Okay.

11
00:00:25,030 --> 00:00:27,250
And then finally we will be returning it over here.

12
00:00:29,230 --> 00:00:29,770
All right.

13
00:00:29,770 --> 00:00:32,680
And we will also be needing a helper function.

14
00:00:32,680 --> 00:00:35,500
And let me just call this function helper itself.

15
00:00:35,500 --> 00:00:38,230
And to this function we will be passing a node.

16
00:00:38,230 --> 00:00:39,280
We can call it root.

17
00:00:39,280 --> 00:00:46,060
And we'll also be passing the remaining sum which we need at a particular instance and the current array.

18
00:00:46,060 --> 00:00:52,930
Now car over here is going to be a combination of elements from the root up to the previous node for

19
00:00:52,930 --> 00:00:54,190
a particular instance.

20
00:00:54,520 --> 00:00:54,910
Okay.

21
00:00:54,910 --> 00:01:00,850
Now inside this function we will be writing the base case as well as the recursive case.

22
00:01:01,330 --> 00:01:04,090
But for now I'm just keeping placeholders over here.

23
00:01:04,090 --> 00:01:05,710
Let's write the details later.

24
00:01:05,710 --> 00:01:09,190
And once we are done with that, we'll have to call the helper function once.

25
00:01:09,190 --> 00:01:13,690
And at that point we'll be passing the root which is given to us, which is this value over here.

26
00:01:13,690 --> 00:01:16,840
And the remaining sum would be the target sum itself.

27
00:01:16,840 --> 00:01:22,330
Because as of now nothing has been added to car, and therefore car is also just going to be an empty

28
00:01:22,330 --> 00:01:22,600
array.

29
00:01:23,020 --> 00:01:23,380
Okay.

30
00:01:23,380 --> 00:01:26,230
So this is the skeleton of the approach that we are going to take.

31
00:01:26,230 --> 00:01:28,600
Now let's go ahead and write the details over here.

32
00:01:28,600 --> 00:01:34,030
Now the base case would be the scenario where the root is equal to null.

33
00:01:35,420 --> 00:01:37,820
And in that case, we will just return.

34
00:01:37,820 --> 00:01:38,210
Okay.

35
00:01:38,210 --> 00:01:39,890
Now this can happen in two ways.

36
00:01:39,890 --> 00:01:45,410
The first way is that if the binary tree itself is empty, and the other case in which this can occur

37
00:01:45,410 --> 00:01:50,840
is once we visit a leaf node, and then if we try to go left or right from there, we would get that

38
00:01:50,840 --> 00:01:53,150
this node over here is equal to null.

39
00:01:53,150 --> 00:01:53,630
Okay.

40
00:01:53,630 --> 00:01:57,710
Now if this is not the case, let's proceed with the recursive case.

41
00:01:57,710 --> 00:02:03,350
Now over here we will have to push the value of this particular node to cur.

42
00:02:03,350 --> 00:02:07,460
So I can say cur dot push root dot val.

43
00:02:08,180 --> 00:02:08,630
Okay.

44
00:02:08,630 --> 00:02:13,580
And we will have to do this even if the remaining sum is negative.

45
00:02:15,970 --> 00:02:16,540
Okay.

46
00:02:16,540 --> 00:02:18,670
And the reason for this is in the question.

47
00:02:18,670 --> 00:02:22,210
It's mentioned that values can have negative values as well.

48
00:02:22,210 --> 00:02:28,210
So let's say at a point, the total value of elements that have been added to the curve is equal to

49
00:02:28,210 --> 00:02:29,020
1 or 2.

50
00:02:29,020 --> 00:02:31,900
And let's say the target sum is equal to 100.

51
00:02:31,900 --> 00:02:32,290
Okay.

52
00:02:32,290 --> 00:02:38,770
Now we can't stop at this point because it could be that the leaf element has a value of minus two.

53
00:02:38,770 --> 00:02:42,520
And in that case 102 minus two would give us 100 okay.

54
00:02:42,520 --> 00:02:43,900
And let's say this is the leaf node.

55
00:02:43,900 --> 00:02:45,490
So that would be a valid case.

56
00:02:45,490 --> 00:02:50,680
So that's why no matter what we will have to push the value of this particular node to occur.

57
00:02:50,890 --> 00:02:58,120
And then we are going to check whether we have arrived at a leaf node where the sum of the values from

58
00:02:58,120 --> 00:03:02,200
the root node up to this particular node is equal to the target sum.

59
00:03:02,200 --> 00:03:03,850
So that's what we are going to check over here.

60
00:03:03,850 --> 00:03:09,370
So for that I'll say if rem sum is equal to root dot val.

61
00:03:10,630 --> 00:03:16,150
Because remember, even though we push this particular value to curb, we have not yet changed REM some,

62
00:03:16,150 --> 00:03:17,620
which is what we got over here.

63
00:03:17,620 --> 00:03:21,250
So that's why we are checking whether rem sum is equal to root dot val.

64
00:03:21,250 --> 00:03:27,190
And that's just a way of checking whether adding this particular value to the current array would result

65
00:03:27,190 --> 00:03:30,640
in a combination whose sum is equal to the target sum.

66
00:03:30,640 --> 00:03:37,270
And if this is true, we would also need to check whether this particular node root is a leaf node.

67
00:03:37,270 --> 00:03:37,660
Okay.

68
00:03:37,660 --> 00:03:47,620
And to check that we will just check whether root dot left is equal to null and root dot right is equal

69
00:03:47,620 --> 00:03:48,340
to null.

70
00:03:48,640 --> 00:03:49,030
Okay.

71
00:03:49,030 --> 00:03:54,370
So if these two things are true that is if rem sum is equal to root dot val.

72
00:03:54,370 --> 00:04:02,290
And if this particular node root is a leaf node, then we have identified a valid root to leaf combination

73
00:04:02,290 --> 00:04:04,240
that adds up to the target sum.

74
00:04:04,240 --> 00:04:10,450
And therefore we would just make a copy of Cur at this particular instance, and we would just push

75
00:04:10,450 --> 00:04:11,860
it to the results array.

76
00:04:11,860 --> 00:04:13,180
So that's what you're doing over here.

77
00:04:13,180 --> 00:04:16,360
And again we have to make a copy because this is a backtracking approach.

78
00:04:16,360 --> 00:04:19,480
And changes to Cur are made in place okay.

79
00:04:19,630 --> 00:04:26,290
And if this is not the case then as we have discussed in the previous video, we will have to explore

80
00:04:26,290 --> 00:04:29,500
going to the left part and to the right part.

81
00:04:29,500 --> 00:04:31,030
So first let's go to the left.

82
00:04:31,030 --> 00:04:32,950
So I will have root dot left over here.

83
00:04:32,950 --> 00:04:38,950
And the remaining sum would have to be updated to rem sum minus root dot val.

84
00:04:38,950 --> 00:04:42,280
Because we added this particular value to curve over here.

85
00:04:42,370 --> 00:04:45,700
And then we'll also have to pass curve to it okay.

86
00:04:45,700 --> 00:04:51,310
And then we'll also have to explore the right path which is helper root dot right.

87
00:04:52,990 --> 00:04:57,670
And then again we have the same rem sum and curve values as we have over here.

88
00:04:57,670 --> 00:04:59,770
So let me just copy and paste it over here.

89
00:05:00,040 --> 00:05:00,730
And that's it.

90
00:05:00,730 --> 00:05:07,000
Now once we are out of this we'll have to do the backtracking step which is curved dot pop okay.

91
00:05:07,000 --> 00:05:08,980
So this is the backtracking step.

92
00:05:10,510 --> 00:05:15,640
And again this is important because probably we would want to go one level up and then visit another

93
00:05:15,640 --> 00:05:17,230
branch in the recursive tree.

94
00:05:17,230 --> 00:05:19,600
So this is how we can solve path sum two.

95
00:05:19,600 --> 00:05:23,620
Now let's go ahead and run this code and see if it's passing all the test cases.

96
00:05:24,370 --> 00:05:25,960
And you can see that it's working.

97
00:05:25,960 --> 00:05:27,880
It's passing all the test cases.