1 00:00:06,470 --> 00:00:15,260 In this section, we are going to talk about another data structure known as a binary search tree in 2 00:00:15,260 --> 00:00:23,630 order to get an understanding of what a binary search tree is a beast, we need to understand that it 3 00:00:23,630 --> 00:00:25,610 has three properties. 4 00:00:30,520 --> 00:00:35,950 The first property is the left subtree. 5 00:00:37,770 --> 00:00:38,760 Of a node 6 00:00:41,820 --> 00:00:43,320 contains 7 00:00:45,060 --> 00:00:50,040 only nodes with lesser 8 00:00:52,050 --> 00:00:53,430 values 9 00:00:55,320 --> 00:00:58,560 than the nodes key. 10 00:01:03,060 --> 00:01:10,650 The second property is very similar, except with it being the left subtree that is going to be the 11 00:01:10,650 --> 00:01:21,300 right subtree, and instead of it being lesser values, it is going to be greater values. 12 00:01:23,580 --> 00:01:33,420 And then the third property is that the left and right subtree must also. 13 00:01:37,320 --> 00:01:40,950 B a binary search tree. 14 00:01:42,490 --> 00:01:47,440 So some additional terminologies that we need to understand is a root node. 15 00:01:51,090 --> 00:01:52,830 It is the top level node. 16 00:01:56,700 --> 00:01:58,440 And then we have a leaf. 17 00:02:00,420 --> 00:02:04,980 Which is a node with zero. 18 00:02:07,420 --> 00:02:08,320 Children. 19 00:02:10,000 --> 00:02:15,580 So if we did a mock tree real quick, this would be our root node. 20 00:02:17,230 --> 00:02:18,700 This would be our. 21 00:02:19,610 --> 00:02:22,340 Left leaf or right leaf. 22 00:02:23,690 --> 00:02:25,200 Now we have another left leaf. 23 00:02:25,220 --> 00:02:28,970 This is no longer a leaf because now we have children here. 24 00:02:28,970 --> 00:02:31,280 So this is now a subtree. 25 00:02:32,060 --> 00:02:34,070 And this is a leaf leaf. 26 00:02:34,070 --> 00:02:35,930 And this is still a leaf. 27 00:02:37,520 --> 00:02:44,780 So now let's look at some values and see how we can insert them. 28 00:02:45,950 --> 00:02:52,580 Because when you want to insert these values, there's a certain way that we need to think about it 29 00:02:52,790 --> 00:02:55,130 in order to ensure. 30 00:02:57,060 --> 00:03:01,200 Excuse me to ensure that our order is done the correct way. 31 00:03:02,670 --> 00:03:06,000 So what we want to do is we want to insert the values. 32 00:03:06,030 --> 00:03:18,330 Eight 310 one 614 four seven. 33 00:03:19,030 --> 00:03:20,080 And 13. 34 00:03:22,240 --> 00:03:23,760 So let's bring this down. 35 00:03:23,770 --> 00:03:27,010 So the first value we want to insert is eight. 36 00:03:27,400 --> 00:03:30,280 So eight is our root node. 37 00:03:33,020 --> 00:03:38,600 And when we insert values, we always start at the root node and then traverse accordingly. 38 00:03:39,020 --> 00:03:42,860 So now we're going to insert the value three. 39 00:03:44,210 --> 00:03:48,320 So with eight being our root node, three is less than eight. 40 00:03:48,770 --> 00:03:54,830 That means we go to the left and we add our three similar with ten. 41 00:03:55,130 --> 00:03:58,550 Ten is greater than eight, so we will add it to the right. 42 00:03:58,880 --> 00:04:03,500 So now three and ten are leaf nodes since they have zero children. 43 00:04:04,520 --> 00:04:06,320 So now we go with one. 44 00:04:07,010 --> 00:04:08,350 One is less than eight. 45 00:04:08,360 --> 00:04:09,650 So go to the left. 46 00:04:11,240 --> 00:04:12,850 One is less than three. 47 00:04:12,860 --> 00:04:14,570 So go to the left again. 48 00:04:17,620 --> 00:04:18,850 Now we have six. 49 00:04:19,330 --> 00:04:20,920 Six is less than eight. 50 00:04:21,400 --> 00:04:23,500 Three is less than six. 51 00:04:23,500 --> 00:04:25,280 So six is greater than three. 52 00:04:25,300 --> 00:04:27,610 So now we have six here. 53 00:04:28,330 --> 00:04:29,440 14. 54 00:04:29,570 --> 00:04:31,750 14 is greater than eight. 55 00:04:32,020 --> 00:04:33,910 14 is greater than ten. 56 00:04:37,700 --> 00:04:40,850 Four is less than eight. 57 00:04:41,510 --> 00:04:43,880 Four is greater than three. 58 00:04:44,450 --> 00:04:46,700 Four is less than six. 59 00:04:49,530 --> 00:04:50,430 Seven. 60 00:04:50,790 --> 00:04:52,620 Seven is less than eight. 61 00:04:52,980 --> 00:04:54,840 Seven is greater than three. 62 00:04:54,870 --> 00:04:56,970 Seven is greater than six. 63 00:04:59,460 --> 00:05:01,410 And finally, 13. 64 00:05:01,440 --> 00:05:03,030 13 is greater than eight. 65 00:05:03,030 --> 00:05:05,010 Which is greater than ten. 66 00:05:05,010 --> 00:05:07,530 Which is less than 14. 67 00:05:07,740 --> 00:05:11,480 So this is what our final tree would look like. 68 00:05:11,490 --> 00:05:14,040 So in here we have a leaf 69 00:05:16,590 --> 00:05:17,400 leaf. 70 00:05:18,700 --> 00:05:19,420 Beef. 71 00:05:21,850 --> 00:05:22,810 And Leif. 72 00:05:23,080 --> 00:05:24,600 And then all of these. 73 00:05:24,610 --> 00:05:27,550 So three subtree is one and six. 74 00:05:27,550 --> 00:05:28,840 Six is a subtree. 75 00:05:28,870 --> 00:05:32,680 Here we have our subtree here. 76 00:05:33,640 --> 00:05:40,270 So this is what it looks like when you try to insert values into a binary search tree. 77 00:05:41,290 --> 00:05:45,070 So overall, the concept is pretty simple to understand. 78 00:05:45,340 --> 00:05:52,960 So now that we have a good understanding of what a binary search tree is, we can begin implementing 79 00:05:52,960 --> 00:05:57,280 one and we will begin implementing our binary search tree. 80 00:05:57,310 --> 00:05:59,080 In the next lecture.