1
00:00:00,830 --> 00:00:01,820
Hi everyone.

2
00:00:01,820 --> 00:00:03,410
Let's do this question.

3
00:00:03,410 --> 00:00:11,390
Write a function that takes the root of a binary tree and returns the level order traversal of its nodes

4
00:00:11,390 --> 00:00:14,720
values that is, from left to right, level by level.

5
00:00:14,720 --> 00:00:16,130
So this is the first part.

6
00:00:16,220 --> 00:00:18,770
Then let's continue reading the question.

7
00:00:18,770 --> 00:00:23,360
And then we will come back and try to think about what it means with level order traversal.

8
00:00:23,360 --> 00:00:30,860
So let's read initially write an instance method for the binary search tree class to insert the values

9
00:00:30,860 --> 00:00:35,510
given as an array into the binary tree from left to right, level by level.

10
00:00:35,510 --> 00:00:40,730
Each value in the array which is not null is to be made a node and added to the tree.

11
00:00:40,760 --> 00:00:41,930
See examples below.

12
00:00:41,930 --> 00:00:45,350
Then write the function mentioned first, which is this one over here.

13
00:00:45,380 --> 00:00:45,770
All right.

14
00:00:45,770 --> 00:00:48,170
So first let's think about the insert function.

15
00:00:48,650 --> 00:00:50,840
Now we will be given an array of values.

16
00:00:50,840 --> 00:00:55,190
So for example if this is the array which is given to us we have to take each value.

17
00:00:55,190 --> 00:00:56,570
So we take the first value.

18
00:00:56,600 --> 00:01:00,290
We make it a node and then we make it the root of the binary tree.

19
00:01:00,290 --> 00:01:04,760
Then we take the next value and we add it over here which is the left of the root.

20
00:01:04,760 --> 00:01:09,230
Then we take the next value we added over here, which is the right of the root right.

21
00:01:09,230 --> 00:01:13,880
And then we keep doing this we take the next value we added over here which is the left of this node.

22
00:01:13,880 --> 00:01:15,260
And we take this value.

23
00:01:15,260 --> 00:01:18,920
We make it a node and we add it over here which is the right of this node.

24
00:01:18,920 --> 00:01:20,660
So this is the insert function.

25
00:01:20,660 --> 00:01:23,480
Now we may also be given values null.

26
00:01:23,480 --> 00:01:25,220
So what do we do in that case.

27
00:01:25,730 --> 00:01:27,320
Let's look at this example.

28
00:01:27,320 --> 00:01:32,090
Over here we have the array 123 null and four and five.

29
00:01:32,090 --> 00:01:35,090
So we take again one and it's made the root.

30
00:01:35,090 --> 00:01:39,470
And two and three are added to its left and right right these nodes.

31
00:01:39,470 --> 00:01:41,000
And then we have null over here.

32
00:01:41,000 --> 00:01:43,610
So the left of two will be null.

33
00:01:44,300 --> 00:01:48,470
And then the right of two will be four, and then we have five, which is the left of three.

34
00:01:48,470 --> 00:01:50,030
So this is how this works.

35
00:01:50,030 --> 00:01:50,300
All right.

36
00:01:50,300 --> 00:01:53,330
So this is the insert function which is mentioned over here.

37
00:01:53,330 --> 00:01:57,770
And this is to be an instance method for the binary search tree class.

38
00:01:57,770 --> 00:01:59,660
So this is something that we have to write.

39
00:01:59,660 --> 00:02:02,420
And then now let's look at the level order traversal.

40
00:02:02,420 --> 00:02:06,770
So we have to write a function for the level order traversal of the binary tree.

41
00:02:06,770 --> 00:02:07,160
All right.

42
00:02:07,160 --> 00:02:08,960
So that is what is mentioned over here.

43
00:02:09,230 --> 00:02:13,850
Now what is it when it what does it what does it mean with level order traversal.

44
00:02:13,850 --> 00:02:20,090
For example for the case of this binary tree over here, we have to return an output array where each

45
00:02:20,090 --> 00:02:22,250
level is put into one array.

46
00:02:22,250 --> 00:02:28,160
For example, over here the first level just has one element and the second level has two and three.

47
00:02:28,160 --> 00:02:31,370
So that's why we have an array with the values two and three over here.

48
00:02:31,370 --> 00:02:33,950
And then the third level has four and five.

49
00:02:33,950 --> 00:02:36,110
So we have an array with four and five over here.

50
00:02:36,110 --> 00:02:38,330
Now what about this binary tree over here.

51
00:02:38,330 --> 00:02:43,460
If you do a level order traversal of this binary tree the output would be one.

52
00:02:43,460 --> 00:02:45,800
Because in this level we just have one.

53
00:02:45,800 --> 00:02:48,470
Then we have two and three which is the second level.

54
00:02:48,470 --> 00:02:51,890
So we have two and three one an array with two and three over here.

55
00:02:51,890 --> 00:02:55,790
And then we have an array with four and five which is this level over here.

56
00:02:55,790 --> 00:02:56,300
All right.

57
00:02:56,300 --> 00:02:57,650
So we have understood the question.

58
00:02:57,650 --> 00:03:02,300
We have to write a function for level order traversal of the given binary tree.

59
00:03:02,300 --> 00:03:06,530
And before we write that function we have to write an insert function.

60
00:03:06,530 --> 00:03:08,810
And we will be given an array of values.

61
00:03:08,810 --> 00:03:10,760
And they have to be created.

62
00:03:10,760 --> 00:03:15,170
Nodes have to be created with those values and inserted into our binary tree.

63
00:03:15,170 --> 00:03:15,650
All right.

64
00:03:15,650 --> 00:03:16,850
So that's the question.

65
00:03:17,270 --> 00:03:20,240
Now let's go ahead and think about a few test cases.

66
00:03:20,240 --> 00:03:22,820
Now the insert function is pretty straightforward.

67
00:03:22,820 --> 00:03:23,990
So we have that over here.

68
00:03:23,990 --> 00:03:27,680
Now let's think about a few test cases about the level order traversal.

69
00:03:27,680 --> 00:03:31,310
Let's say the binary tree which is given to us is this one over here.

70
00:03:31,310 --> 00:03:32,930
Now what would be the output.

71
00:03:32,930 --> 00:03:36,710
The output would be 711 comma one and 539.

72
00:03:36,710 --> 00:03:36,920
Right.

73
00:03:36,920 --> 00:03:38,030
Seven is one level.

74
00:03:38,030 --> 00:03:40,490
Then we have 11 and one which is one level.

75
00:03:40,490 --> 00:03:44,660
And then over here in this level we have five, three and nine.

76
00:03:44,660 --> 00:03:46,220
So that's 539 over here.

77
00:03:46,220 --> 00:03:50,810
Now what if the binary tree is just having a root node right.

78
00:03:50,810 --> 00:03:52,400
For example this is the case.

79
00:03:52,400 --> 00:03:54,860
It just has one node which is the root node.

80
00:03:54,860 --> 00:03:58,610
In this case the output array will just have one element.

81
00:03:58,610 --> 00:04:01,370
And that would be an array with just the element seven.

82
00:04:01,370 --> 00:04:06,350
And if the binary tree is empty then we will just return an empty array.

83
00:04:06,350 --> 00:04:10,790
Now again remember you can come up with the test cases along with your interviewer.

84
00:04:10,790 --> 00:04:17,090
So it will be good if you ask the interviewer whether it's okay that you come together up with the test

85
00:04:17,090 --> 00:04:21,050
cases, because that will ensure that you are on the same page and you have understood the question

86
00:04:21,050 --> 00:04:21,650
properly.

87
00:04:21,650 --> 00:04:26,690
For example, you can ask, what should I do if the, uh, the, uh, the binary tree which is given

88
00:04:26,690 --> 00:04:28,400
to me is just a null tree.

89
00:04:28,400 --> 00:04:32,870
So then probably the interviewer says, in that case you can just return an empty array.

90
00:04:32,870 --> 00:04:35,630
So this is something that you have to agree with the interviewer.

91
00:04:35,630 --> 00:04:36,140
All right.

92
00:04:36,140 --> 00:04:37,670
So we have understood the question.

93
00:04:37,670 --> 00:04:40,490
And we have also looked at some test cases.

94
00:04:40,490 --> 00:04:41,630
In the next video.

95
00:04:41,630 --> 00:04:45,800
Let's first discuss the method or how we can write the insert function.

96
00:04:45,800 --> 00:04:49,640
And after that we will take a look at the level order traversal function.