1
00:00:00,600 --> 00:00:01,530
Hi everyone.

2
00:00:01,530 --> 00:00:05,520
In this video let's try to understand what is a binary search tree.

3
00:00:05,550 --> 00:00:08,250
Now, as the name suggests, this is a binary tree.

4
00:00:08,250 --> 00:00:10,920
So every node can have at the most two children.

5
00:00:10,920 --> 00:00:13,200
And this is sorted in a special manner.

6
00:00:13,200 --> 00:00:15,960
Now the values over here for the nodes will be integers.

7
00:00:15,960 --> 00:00:21,810
And it's sorted in this manner such that for every node, the values of the nodes to the left of that

8
00:00:21,810 --> 00:00:24,750
particular node will be less than the value of the node.

9
00:00:24,750 --> 00:00:27,510
So for example, you have a node over here which is ten.

10
00:00:27,510 --> 00:00:32,580
Now if you have a node to its left, this value which is there in this node has to be less than ten.

11
00:00:32,580 --> 00:00:34,440
So for example it can be five.

12
00:00:34,440 --> 00:00:40,290
Now it's also true that the nodes which are to the right of this particular node should have a value

13
00:00:40,290 --> 00:00:42,450
which is greater than the value of the node.

14
00:00:42,450 --> 00:00:47,970
So to the right of this ten I should have some value, which is for example, let's say 20 because 20

15
00:00:47,970 --> 00:00:48,930
is greater than ten.

16
00:00:48,930 --> 00:00:52,290
Now let me just have a point mentioned over here.

17
00:00:52,290 --> 00:00:58,200
In some cases, if there are, the binary search tree allows an equal value to be entered, we would

18
00:00:58,200 --> 00:01:03,990
define that the binary search tree is such that the values to the left are strictly less, and to the

19
00:01:03,990 --> 00:01:07,050
right probably are greater than or equal to.

20
00:01:07,050 --> 00:01:12,150
So again, it depends on how the BST is defined for a particular question.

21
00:01:12,150 --> 00:01:12,600
All right.

22
00:01:12,630 --> 00:01:14,850
Now let's go ahead and take an example.

23
00:01:14,850 --> 00:01:16,290
So over here you have a BST.

24
00:01:16,320 --> 00:01:18,930
You can see that over here the value is 54.

25
00:01:18,930 --> 00:01:23,160
And every value to the left of 54 is less than 54.

26
00:01:23,160 --> 00:01:28,890
And if we go with this definition where we say that the values to the right has to be greater, and

27
00:01:28,890 --> 00:01:31,860
again, it depends on how we define it for any particular question.

28
00:01:31,860 --> 00:01:37,080
So if you get a question on a BST, definitely ask the interviewer whether equal values are allowed

29
00:01:37,080 --> 00:01:37,560
or not.

30
00:01:37,560 --> 00:01:44,190
And what to do if equal values are allowed, typically with equal values will not be allowed, and if

31
00:01:44,190 --> 00:01:49,920
they are allowed, as we have in one of the questions in this section where we deal with the BST construction.

32
00:01:49,920 --> 00:01:52,500
So in that question greater equal values are allowed.

33
00:01:52,500 --> 00:01:57,330
And there we have defined that the value, if it's equal also should be entered to the right.

34
00:01:57,330 --> 00:02:00,300
So again it depends on how we define our BST.

35
00:02:00,420 --> 00:02:03,840
Now over here we have defined that the values to the right has to be greater.

36
00:02:03,840 --> 00:02:07,290
So you can see that these values are greater than 54.

37
00:02:07,470 --> 00:02:07,920
All right.

38
00:02:07,950 --> 00:02:10,260
Now the same holds true for every node.

39
00:02:10,260 --> 00:02:12,240
So for example if you take a look at this.

40
00:02:12,240 --> 00:02:13,530
So over here we have 50.

41
00:02:13,560 --> 00:02:16,740
Now towards its left the value is less than 50.

42
00:02:16,740 --> 00:02:20,010
And towards the right of 50 the value is greater than 50.

43
00:02:20,010 --> 00:02:21,930
And that's also holding true over here.

44
00:02:21,930 --> 00:02:24,990
This is 70 which is greater than 65.

45
00:02:24,990 --> 00:02:25,230
Right.

46
00:02:25,230 --> 00:02:28,650
So whatever is coming over here is greater than 65.

47
00:02:28,650 --> 00:02:31,470
So again it's following the BST property.

48
00:02:32,310 --> 00:02:34,170
Now we have understood what a BST is.

49
00:02:34,170 --> 00:02:34,410
Now.

50
00:02:34,410 --> 00:02:36,480
This is a very important data structure.

51
00:02:36,840 --> 00:02:42,600
Now let's take a quick look at the bigger analysis of common operations for a binary search tree.

52
00:02:42,630 --> 00:02:46,080
Now we have a future video where we discuss this in great detail.

53
00:02:46,080 --> 00:02:48,210
So we are just glancing over it over here.

54
00:02:48,240 --> 00:02:54,300
Now you can see that inserting, searching and deletion for a binary search tree is on average an O

55
00:02:54,300 --> 00:02:55,590
of log n operation.

56
00:02:55,590 --> 00:03:00,450
Now, the intuitive way to understand this is that if you double the number of nodes, the number of

57
00:03:00,450 --> 00:03:02,670
steps will only increase by one.

58
00:03:02,670 --> 00:03:06,180
So we have seen that this pattern over here is represented by log n.

59
00:03:06,180 --> 00:03:07,590
Now let's take an example.

60
00:03:07,590 --> 00:03:10,290
So over here this BST has only three nodes.

61
00:03:10,290 --> 00:03:12,480
And this BST over here has six nodes.

62
00:03:12,480 --> 00:03:13,980
So we have doubled the number of nodes.

63
00:03:13,980 --> 00:03:17,430
Now let's say we want to insert a node with the value 24.

64
00:03:17,430 --> 00:03:22,170
Now if you're doing it in this BST we will do one check where we check the value of 15.

65
00:03:22,170 --> 00:03:24,360
We see that 24 is greater than 15.

66
00:03:24,360 --> 00:03:26,010
So we move in the right direction.

67
00:03:26,010 --> 00:03:27,690
Then we do a second check.

68
00:03:27,690 --> 00:03:31,380
We see that we have 20 over here and 24 is greater than 20.

69
00:03:31,380 --> 00:03:33,840
So we insert it towards the right over here.

70
00:03:33,840 --> 00:03:35,850
So you can see we are doing two operations.

71
00:03:35,850 --> 00:03:36,450
Now.

72
00:03:36,450 --> 00:03:39,210
Over here we have six nodes which is double the number of nodes.

73
00:03:39,210 --> 00:03:44,700
And again if you want to insert 24 in its correct position so that the BST property is fulfilled, we

74
00:03:44,700 --> 00:03:45,780
have to do one check.

75
00:03:45,780 --> 00:03:46,950
We see 15.

76
00:03:46,950 --> 00:03:48,570
We see 24 is greater than 15.

77
00:03:48,570 --> 00:03:50,040
We move in the right direction.

78
00:03:50,040 --> 00:03:51,180
The second check is over here.

79
00:03:51,180 --> 00:03:54,000
We see that 20 and 24 is greater than 20.

80
00:03:54,030 --> 00:03:57,150
We move in the right direction and then we have 25 over here.

81
00:03:57,150 --> 00:03:59,400
And we know 24 is less than 25.

82
00:03:59,400 --> 00:04:02,550
So we move in the left direction and we can insert it over here.

83
00:04:02,550 --> 00:04:06,540
So you can see that we are doing three operations when we double the number of nodes.

84
00:04:06,540 --> 00:04:08,490
And over here we are just doing two operations.

85
00:04:08,490 --> 00:04:10,410
So that's the intuitive way to look at it.

86
00:04:10,410 --> 00:04:13,170
That's why the time complexity is O of log n.

87
00:04:13,170 --> 00:04:15,270
But then we are not covering it in detail over here.

88
00:04:15,270 --> 00:04:18,450
Because again as I said, we are covering it in a future video.

89
00:04:18,450 --> 00:04:21,870
And there the time complexity is analyzed in great detail.

90
00:04:21,870 --> 00:04:24,540
Now why is the worst case O of n?

91
00:04:24,540 --> 00:04:26,220
Let's quickly cover that also.

92
00:04:26,220 --> 00:04:30,000
Now if we have a BST that looks like this.

93
00:04:30,670 --> 00:04:34,090
You can notice that this is actually a valid binary search tree, right?

94
00:04:34,090 --> 00:04:36,910
Everything to the right of ten is greater than ten.

95
00:04:36,910 --> 00:04:42,430
Everything to the right of 12 is greater than 12, everything to the right of 20 is greater than 20,

96
00:04:42,430 --> 00:04:42,850
etc..

97
00:04:42,850 --> 00:04:44,740
So this is a valid binary search tree.

98
00:04:44,770 --> 00:04:50,410
Now over here, if you want to insert something we'll have to go all the way to probably we'll have

99
00:04:50,410 --> 00:04:51,250
to go all the way over here.

100
00:04:51,250 --> 00:04:51,400
Right.

101
00:04:51,400 --> 00:04:55,930
For example, if you wanted to insert 60 now that would be n operations.

102
00:04:55,930 --> 00:04:58,750
So we are traversing the entire binary search tree.

103
00:04:58,750 --> 00:05:01,510
So that's why the worst case is O of n.

104
00:05:01,510 --> 00:05:06,490
Now the solution or the way to avoid this is it's better to pick a different root.

105
00:05:06,490 --> 00:05:08,980
Right over here the root node is ten.

106
00:05:08,980 --> 00:05:11,410
But let's say you pick 20 as the root node.

107
00:05:11,410 --> 00:05:14,710
And in that case the binary search tree would look quite different.

108
00:05:14,710 --> 00:05:15,070
Right.

109
00:05:15,070 --> 00:05:17,260
Let's quickly try to draw that over here.

110
00:05:17,740 --> 00:05:19,690
Now let's say we have 20 as the root node.

111
00:05:19,690 --> 00:05:20,770
So that's 20.

112
00:05:20,770 --> 00:05:22,810
And let's try to insert these nodes.

113
00:05:22,810 --> 00:05:24,700
Let's say we insert 12 and 30.

114
00:05:24,700 --> 00:05:28,030
So 12 is to its left and then 30 is to its right.

115
00:05:28,030 --> 00:05:29,860
Again we can do this in multiple ways.

116
00:05:29,860 --> 00:05:30,970
I'm just doing one way.

117
00:05:30,970 --> 00:05:32,470
And then you have ten over here.

118
00:05:32,470 --> 00:05:33,970
Now ten is less than 12.

119
00:05:33,970 --> 00:05:35,440
So it's over here inserted.

120
00:05:35,440 --> 00:05:37,450
And then we have 50.

121
00:05:37,450 --> 00:05:38,500
50 is greater than 30.

122
00:05:38,500 --> 00:05:39,550
So it's inserted over here.

123
00:05:39,550 --> 00:05:44,410
Now if we want to insert 60 you can see we go from 20 to 30 to 50.

124
00:05:44,410 --> 00:05:45,640
And then we insert it over here.

125
00:05:45,640 --> 00:05:49,330
So you can see that the number of operations has reduced to log n right.