1
00:00:00,680 --> 00:00:01,700
Welcome back.

2
00:00:01,700 --> 00:00:05,480
In this video let's discuss how we can implement this recursively.

3
00:00:05,690 --> 00:00:07,670
This is also going to be pretty straightforward.

4
00:00:07,670 --> 00:00:09,860
So we have our binary tree over here.

5
00:00:09,860 --> 00:00:12,200
And we start at the root node.

6
00:00:12,200 --> 00:00:15,590
So we call the recursive function for the root node.

7
00:00:15,590 --> 00:00:20,660
And what this function will do is it will swap its children so its children are two and three.

8
00:00:20,660 --> 00:00:21,860
So let's swap them.

9
00:00:21,860 --> 00:00:24,230
So we get three and two over here.

10
00:00:24,230 --> 00:00:24,590
All right.

11
00:00:24,620 --> 00:00:28,070
Now we are just going to proceed in the left direction.

12
00:00:28,070 --> 00:00:30,050
So we will go in this direction.

13
00:00:30,050 --> 00:00:34,970
And we will recursively call the same function for this particular node over here.

14
00:00:34,970 --> 00:00:36,890
Now again what will it do.

15
00:00:36,890 --> 00:00:41,960
It will come inside the recursive function and it will swap its children which is null and seven.

16
00:00:41,960 --> 00:00:44,360
So we will get the binary tree in this way.

17
00:00:44,360 --> 00:00:45,530
So we have seven and null.

18
00:00:45,530 --> 00:00:46,910
So these two have been swapped.

19
00:00:46,910 --> 00:00:47,540
All right.

20
00:00:47,540 --> 00:00:50,210
Again we will recursively make the same call.

21
00:00:50,210 --> 00:00:53,180
The we will call the same function over here for this.

22
00:00:53,180 --> 00:00:54,920
That is we moved in the left direction.

23
00:00:54,920 --> 00:00:56,150
So you can see we moved.

24
00:00:56,150 --> 00:00:57,710
We are moving in the left direction right.

25
00:00:57,710 --> 00:00:59,810
So we have this node over here.

26
00:00:59,810 --> 00:01:02,360
And its children are just null and null.

27
00:01:02,360 --> 00:01:06,230
So we are going to swap them but it's not going to have any impact.

28
00:01:06,230 --> 00:01:12,110
And then after that we will again call the function recursively on the null node over here which is

29
00:01:12,110 --> 00:01:12,860
null right.

30
00:01:12,860 --> 00:01:15,200
And at that case we are just going to return.

31
00:01:15,200 --> 00:01:16,940
So that is going to be our base case.

32
00:01:16,940 --> 00:01:19,550
So if the node is going to be null we will just return.

33
00:01:19,550 --> 00:01:20,600
So that is our base case.

34
00:01:20,600 --> 00:01:24,110
So when we call it for this node which is null we will return.

35
00:01:24,650 --> 00:01:26,600
And it'll go in the right direction.

36
00:01:26,600 --> 00:01:28,880
Again, it's going to be null and it's going to return.

37
00:01:28,880 --> 00:01:30,530
So it's done for this part.

38
00:01:30,560 --> 00:01:30,980
All right.

39
00:01:30,980 --> 00:01:35,750
So we went in this direction from node three in the left direction.

40
00:01:35,750 --> 00:01:37,520
And it will return at this point.

41
00:01:37,520 --> 00:01:37,940
Right.

42
00:01:37,940 --> 00:01:39,950
Again we are going to call in the right direction.

43
00:01:39,950 --> 00:01:42,590
So we will make the recursive call on this node.

44
00:01:42,590 --> 00:01:43,580
Again this is null.

45
00:01:43,580 --> 00:01:46,010
So it's going to return because that is our base case.

46
00:01:46,010 --> 00:01:47,780
So this also will return.

47
00:01:48,230 --> 00:01:49,940
So at this point this is done.

48
00:01:49,940 --> 00:01:52,070
So this was the left of node one right.

49
00:01:52,070 --> 00:01:53,330
So again it will return.

50
00:01:53,330 --> 00:01:55,040
So the left of node one is done.

51
00:01:55,040 --> 00:01:57,110
Now we are going to go in the right direction.

52
00:01:57,110 --> 00:02:01,970
And we will make the recursive call on this node over here which will just swap its children.

53
00:02:01,970 --> 00:02:04,280
So these two are going to be swapped.

54
00:02:04,280 --> 00:02:06,440
And we get the binary tree in this way.

55
00:02:06,440 --> 00:02:08,210
So you can see that they were swapped.

56
00:02:08,210 --> 00:02:10,580
Now we will again proceed in the left direction.

57
00:02:10,580 --> 00:02:14,060
From here we will make the recursive call on this node over here.

58
00:02:14,060 --> 00:02:16,970
And it will swap its children which are just null and null.

59
00:02:16,970 --> 00:02:19,010
And then we go in the left direction right.

60
00:02:19,010 --> 00:02:20,720
So this is null and this is null.

61
00:02:20,720 --> 00:02:22,610
So from here we will go in the left direction.

62
00:02:22,610 --> 00:02:24,590
And this is because this is null.

63
00:02:24,590 --> 00:02:25,640
This will just return.

64
00:02:25,640 --> 00:02:28,400
Similarly we go in the right direction because this is null.

65
00:02:28,400 --> 00:02:29,420
It will just return.

66
00:02:29,420 --> 00:02:31,160
So it will return from here.

67
00:02:31,160 --> 00:02:35,750
So the left of this call right when the node was two the left call is done.

68
00:02:35,750 --> 00:02:37,910
So now we proceed in the right direction.

69
00:02:37,910 --> 00:02:40,340
And we will make the call on this node over here.

70
00:02:40,340 --> 00:02:44,030
And again it will swap its children which is which are just null and null.

71
00:02:44,030 --> 00:02:45,260
So it has no impact.

72
00:02:45,260 --> 00:02:48,470
And then from there we proceed in the left direction.

73
00:02:48,470 --> 00:02:52,160
We will make the call on this node which is null which will just return.

74
00:02:52,160 --> 00:02:56,630
Then we proceed in the right right direction which will make the call on this node which is also null.

75
00:02:56,630 --> 00:02:57,740
So it will also return.

76
00:02:57,740 --> 00:02:59,090
So this part is done.

77
00:02:59,090 --> 00:03:02,150
Now this will just return and then it will again return and we are done.

78
00:03:02,150 --> 00:03:04,970
So this is how the recursive function works.

79
00:03:04,970 --> 00:03:07,880
You can see that we passed in this binary tree.

80
00:03:07,880 --> 00:03:09,650
And then we got it inverted.

81
00:03:09,650 --> 00:03:11,570
Or we are getting its mirror image.

82
00:03:11,570 --> 00:03:15,470
Now let's take a quick look at its space and time complexity.

83
00:03:15,470 --> 00:03:17,720
And this is a recursive function.

84
00:03:17,720 --> 00:03:22,250
You can see that the time complexity of this solution is O of n itself.

85
00:03:22,250 --> 00:03:27,380
And we have seen that in the case of the iterative iterative solution also we are getting time complexity

86
00:03:27,380 --> 00:03:28,250
of O of n.

87
00:03:28,250 --> 00:03:30,290
Now you can think of it in this manner.

88
00:03:30,290 --> 00:03:35,030
We are traversing every node one time and then we are just swapping its children.

89
00:03:35,030 --> 00:03:35,330
Right.

90
00:03:35,330 --> 00:03:40,670
So we are doing this operation n times, or they are going to be a total of n recursive calls.

91
00:03:40,670 --> 00:03:41,150
Right.

92
00:03:41,150 --> 00:03:45,800
And I'm not saying that they will be there at the same time, but I'm saying that the total number of

93
00:03:45,800 --> 00:03:50,480
operations that we are doing is going to be n now, whenever we are having the recursive call, we are

94
00:03:50,480 --> 00:03:55,940
just calling, we are swapping its children, and then we will recursively call the same function on

95
00:03:55,940 --> 00:03:57,260
its left and right child.

96
00:03:57,260 --> 00:03:59,600
Now that has already been accounted.

97
00:03:59,600 --> 00:04:05,900
When I say when I say that there they are going to be a total of n n calls on the same recursive function.

98
00:04:05,900 --> 00:04:08,720
So for each call we are just swapping its children.

99
00:04:08,720 --> 00:04:11,330
So that's why we are traversing every node one time.

100
00:04:11,330 --> 00:04:14,270
And hence the time complexity is just going to be O of n.

101
00:04:14,270 --> 00:04:16,340
Now what about the space complexity?

102
00:04:16,340 --> 00:04:23,180
The space complexity is because this is a recursive function is going to be O of the maximum depth because

103
00:04:23,180 --> 00:04:23,960
of the call stack.

104
00:04:23,960 --> 00:04:24,290
Right.

105
00:04:24,290 --> 00:04:27,680
And remember the maximum depth is nothing but the height of the tree.

106
00:04:27,680 --> 00:04:29,840
And this is because of the call stack.

107
00:04:29,840 --> 00:04:30,080
Right.

108
00:04:30,080 --> 00:04:35,060
So we are not using any other space, but because of this space you used on the call stack.

109
00:04:35,060 --> 00:04:38,480
That's why the space complexity is O of max depth.

110
00:04:38,480 --> 00:04:44,240
Now for example, in the in this case over here, what what would be the total number of calls that

111
00:04:44,240 --> 00:04:44,810
can be there.

112
00:04:44,810 --> 00:04:49,100
At the same time, we can have a call over here, over here, over here and over here.

113
00:04:49,100 --> 00:04:49,280
Right.

114
00:04:49,280 --> 00:04:54,410
Because its child is null, you can see that there are total of four calls over here right now.

115
00:04:54,830 --> 00:04:59,990
In the case of a balanced binary tree, the maximum depth is going to be log n.

116
00:04:59,990 --> 00:05:06,230
And that's why we can say that the space complexity is O of log n in the case of a balanced binary tree.