1 00:00:00,420 --> 00:00:04,800 ‫So now we're going to create our binary search tree constructor. 2 00:00:05,100 --> 00:00:11,730 ‫But before we get to that, we have to create our node class for a binary search tree. 3 00:00:11,970 --> 00:00:19,410 ‫And as we have discussed previously, this node is similar to an unordered map that looks like this. 4 00:00:19,560 --> 00:00:24,990 ‫And we'll create our member variables for our node class like this. 5 00:00:25,320 --> 00:00:32,370 ‫And then we'll have a constructor for the node class that we pass a value, and we'll set this value 6 00:00:32,370 --> 00:00:33,850 ‫to be equal to value. 7 00:00:33,870 --> 00:00:37,290 ‫This is the same as we saw in a linked list node. 8 00:00:37,620 --> 00:00:41,730 ‫And then we'll set left and right to be equal to null pointer. 9 00:00:42,150 --> 00:00:46,080 ‫So now we can start building our binary search tree class. 10 00:00:46,350 --> 00:00:51,390 ‫So for the first thing I want to explain in building the binary search tree class, I'm going to bring 11 00:00:51,390 --> 00:00:55,560 ‫up a node and make it part of a tree like this. 12 00:00:55,920 --> 00:01:02,010 ‫So all of these nodes need to have something pointing to them or you're not able to get to them. 13 00:01:02,310 --> 00:01:08,790 ‫And you can see that all of these nodes have something pointing to them, the node above it, except 14 00:01:08,790 --> 00:01:09,960 ‫for one. 15 00:01:10,410 --> 00:01:13,570 ‫And we saw this with linked lists. 16 00:01:13,590 --> 00:01:18,360 ‫We have to have something pointing to that first node we call that head. 17 00:01:18,630 --> 00:01:20,520 ‫That is a requirement. 18 00:01:20,520 --> 00:01:23,120 ‫Tail is not a requirement. 19 00:01:23,130 --> 00:01:30,420 ‫We saw that when we used a linked list to implement a stack where we had top, but we didn't have bottom. 20 00:01:30,630 --> 00:01:34,050 ‫So I'm going to put this back as a binary search tree. 21 00:01:34,320 --> 00:01:40,500 ‫And what we're going to call the variable that points to that top node is we're going to call it root. 22 00:01:41,240 --> 00:01:48,140 ‫So now I'm going to bring this code back and our one member variable that we're going to have is going 23 00:01:48,140 --> 00:01:49,640 ‫to be called root. 24 00:01:50,210 --> 00:01:56,120 ‫So now let's create the constructor and we'll focus just in on this. 25 00:01:56,570 --> 00:01:58,220 ‫We're passing this a value. 26 00:01:58,250 --> 00:02:03,440 ‫We use that to create a node like this. 27 00:02:04,210 --> 00:02:09,700 ‫That will say route equals new node like this. 28 00:02:10,120 --> 00:02:16,450 ‫And this is how we have created our constructors up to this point in linked list, doubly link list, 29 00:02:16,450 --> 00:02:18,070 ‫stacks and Qs. 30 00:02:18,190 --> 00:02:25,510 ‫We created the first node at the time that we created a particular instance of that data structure. 31 00:02:25,930 --> 00:02:31,960 ‫Doing it this way is completely valid, but I'm going to show a different way of doing this. 32 00:02:32,320 --> 00:02:39,790 ‫Instead of creating the first node at the time that we create the binary search tree, we can also create 33 00:02:39,790 --> 00:02:44,290 ‫the binary search tree to be empty at the time that we create it. 34 00:02:44,620 --> 00:02:50,980 ‫And then we put the first node in the binary search tree with the insert function. 35 00:02:51,370 --> 00:02:58,210 ‫So I'm going to bring back our code and our constructor and change it to make it do this. 36 00:02:58,210 --> 00:03:00,400 ‫And I'll go through line by line. 37 00:03:00,700 --> 00:03:05,110 ‫So that first line, we don't need to pass this a value. 38 00:03:05,140 --> 00:03:12,400 ‫The only reason we pass this a value was to create the first node so we can remove this. 39 00:03:13,000 --> 00:03:18,610 ‫This line creates that first node so we don't need this. 40 00:03:18,940 --> 00:03:25,540 ‫And then instead of saying root equals new node, we're going to set it equal to null pointer. 41 00:03:26,080 --> 00:03:31,390 ‫So if we're going to create a binary search tree this way, this is all that we need. 42 00:03:31,390 --> 00:03:37,390 ‫And the constructor, you could do something similar to this with linked lists where you set head and 43 00:03:37,390 --> 00:03:42,430 ‫tail to be equal to null pointer and set the length to be equal to zero. 44 00:03:42,790 --> 00:03:48,250 ‫So now let's put this new updated constructor in with the rest of our code. 45 00:03:48,520 --> 00:03:52,900 ‫That is our entire binary search tree class so far. 46 00:03:53,290 --> 00:03:57,130 ‫And now let's go over to VZ code and take a look at this. 47 00:03:57,760 --> 00:04:02,830 ‫So there is our code for our node class there and I'm going to scroll up. 48 00:04:03,790 --> 00:04:08,590 ‫And this is the code that we just looked at for the binary search tree class. 49 00:04:08,980 --> 00:04:14,500 ‫This line creates a new binary search tree called my binary search tree. 50 00:04:14,950 --> 00:04:21,070 ‫And then with this line, what I want to do is I want to do a see out and show the root. 51 00:04:21,070 --> 00:04:23,980 ‫And obviously this is going to be equal to null pointer. 52 00:04:24,310 --> 00:04:31,810 ‫But to get access to the root, I need to come back up here and change this from private to public. 53 00:04:33,480 --> 00:04:37,400 ‫Otherwise we can't access that from the main function. 54 00:04:37,410 --> 00:04:43,620 ‫So now I'm going to run this and you can see that the root is pointing to null pointer. 55 00:04:44,220 --> 00:04:49,830 ‫So it looks like we have a working binary search tree constructor.