00:00Hey there! Let's build a binary search tree together. If you've seen my previous videos,
00:05you understand now how to define a binary search tree, meaning what are the rules
00:09that you have to like adhere to if you want your thing to be a binary search tree.
00:14Also terminology, we're in previous videos. So in this video, we're just going to take a bunch
00:19of random numbers and we're just going to start dropping them into our tree and see how the tree
00:24builds itself out. We have to build our tree in a specific way if it's going to be valid.
00:29We're not going to rearrange our tree and try to make it super pretty. This is going to be like
00:32a
00:32real binary search tree. It might not be pretty, but it'll be real. Let's see if I can find those
00:37numbers that I was going to set up. Okay. So for this particular video, I think I'm going to do
00:47two
00:48videos. I want to build a binary search tree using the following numbers. They're not special. They're
00:54going to produce a tree that is okay. Not perfect. But what I mean to say when I say inserting
01:01these
01:02numbers is one by one, we'll look at each number and we'll drop it in the tree and we'll see
01:07where
01:07it falls according to binary search tree rules of insertion. Then we'll just go to the next number
01:11and then the next and the next. When we're done, we should have a tree. And if you follow along
01:16at
01:17home and you use the right rules to build your tree, then if we use the same sequence of numbers
01:22to build the tree, we should end up with identical trees. They won't suddenly be different.
01:26They're deterministic. Okay. So the first thing that we should try to understand is
01:32when we want to insert a node, the 73 node right here, the first thing we should ask ourselves is,
01:38do we actually have a root node for our binary search tree yet? Right now, the answer is no.
01:43This is just a blank tree. There's nothing in it, which means that first number is going to be the
01:47root node. You might be tempted to say, no, that's a sucky root node. Let's do something else.
01:53Well, I don't know. I mean, you just have to let the numbers fall where they're going to fall
01:58just because a number seems to suck as a root node doesn't mean it's not going to be the root
02:03node. If it's the first thing you added, it's going to be the root node. Don't try to change it
02:07or you're going to mess. You're going to end up with topology that doesn't match
02:10whatever system or person is trying to grade your work or evaluate your work.
02:16So we have no root node. That means the 73 is just going to be the root node of the
02:20entire tree.
02:22We're now done with 73. I'm going to duplicate this slide real fast and we'll say now it's time
02:27to try to add the 98. You know what? I can, I think I can do better than that arrow.
02:32I can make
02:32a nice cute arrow with this program. I'm going to do this. Can I like, hang on one more, one
02:42more
02:42try. Nice. Okay. So now let's add the 98 node. The first thing we have to ask is, do we
02:49have a root
02:49node? Yes. We can't actually put the 98 there. We now have to make a decision. If you recall in
02:56my
02:56previous videos, the lesser values go on the left and the greater values go on the right.
03:02in these trees, which we're not going to support duplicate values with. If you wanted to support
03:07duplicate values, you could do something like less than or equal to would be on the left and
03:10greater than on the right. There's a bunch of other ways you can do it, but I'm just going to
03:14say no
03:14duplicate values in our trees. So we look at the 73 node and we ask, you know, is that, is
03:20that where
03:21our 98 is going to go? It can't go there because 73 exists. Now we have to ask the question,
03:27does 98
03:27belong on the left side or the right side of the 73? Well, because 98 is greater than 73, it
03:34belongs
03:34on the right side, which means I'm going to duplicate this node over here. And I'm going to
03:39try to draw this well, which means basically splitting the difference in terms of the empty
03:44space and trying to keep the same rank as we go down one level of descendancy or like one generation
03:51down at a time. So the next time I go down a level, let's say I do a left child
03:55in the future,
03:57it should be at the same level as the new node I just added. So I did a duplicate and
04:01I forgot to
04:01change the number. And then I'm going to do a line to connect the 73 and the 98. So now
04:12the 73 has a right
04:13child, which is 98. The 98 has a parent, which is 73. And we're done adding the 98. We have
04:20to just
04:20move on to the next number. Okay. So I'm going to move on to the 12. Again, we look at
04:26the root node.
04:27It's occupied. We cannot put the 12 right there on the 73. We have to make a decision. Do we
04:32go to the
04:32left or the right of the 73? 12 is less than 73. So it belongs on the left side. So
04:38that means our
04:39decision now is to jump to the left side. Notice how the left side, there's no child on the left.
04:46That means that's where the new node is going to go. So I'm just going to like select this,
04:50duplicate it real fast, maybe stick it on the same vertical coordinate, and then also try to split the
04:57difference on the screen just to make it look pretty. I'm going to update that 98 so that it is
05:01now the 12. I'm going to add the line that connects the 73 with its new left child 12.
05:09And then we're done adding the 12. Okay, no problem so far. We then are ready to try to add
05:15the 45.
05:16Maybe I should squish this a little bit. Nope, that looks gross. No, that's okay. We'll do that.
05:22We're going to add the 45. Again, we look at the root node. It already exists. So we can't put
05:27the 45
05:27there. Instead, we will just kind of decide, does the 45 belong on the left or the right of the
05:3473?
05:35Okay, well, belongs on the left because it's less than 73. So that means I'm now going to make a
05:42little
05:42decision. I'm going to jump down to the left. If you're in some code, you're following the left
05:47child pointer down. But notice how the left child pointer or the left child, it already exists. So we
05:52can't actually put 45 right there. We have to make another decision. Does 45 belong on the left or the
05:58right of the 12? Well, it's greater than 12. So it belongs on the right side of 12. So I'm
06:03going to
06:03highlight this and duplicate it. I guess I'll just do it that way. Then I'm going to update that number
06:14with 45. And then I'm going to connect the 12 and the 45 with the line. So now 45 is
06:20the right child
06:21of 12 and 12 is the parent of 45. It's at this point that a lot of people start to
06:27get frustrated
06:27with me and they say, well, how come, how come the 12 is like all the way to the left
06:31and the 45 is
06:32like, didn't become like, you know, a level higher because it kind of seems like it's closer to 73.
06:37Shouldn't the 12 be hanging off the left child of the 45? No, no, no, no, no. Don't rearrange the
06:41nodes
06:41as you're building the tree. Just let the numbers, let the nodes fall wherever they're supposed to go.
06:48Another tip is if you're building a tree that has other data types, as the T types inside of the
06:54nodes,
06:54as the template types inside of the nodes. For example, right now I'm just using integers, right?
06:59The T type is int, at least in my mind. If you wanted to put dinosaur objects in the tree,
07:06all you'd have to do is make sure that your code for your dinosaur class, for your dinosaur object,
07:11had its inequality operators implemented, you know, less than, greater than. And then the tree
07:17would still know where to put all the objects. So you could make any kind of custom object you want
07:22and they would all fall in their correct places in the tree as long as the operators actually worked.
07:28Just as a side note. Okay, so now we're ready to add the next item. So I'm going to erase
07:32this stuff
07:33here and I'm going to move the arrow from the 45 to the 67. So now we're going to try
07:38to add the 67.
07:40We look at the root node, it's occupied. We should go to the left because 67 is less than 73.
07:46We look at the 12, that's occupied. So we go left or right. We should go to the right because
07:5067 is
07:51greater than 12. So we look at the 45. Again, it's occupied. There's a node there. So we have to
07:57make another decision. Do we go to the left or to the right? Well, 67 is greater than 45. So
08:02it goes
08:02on the right side. So I'm going to duplicate this off to the right side and down a rank. And
08:08we'll call
08:09that the right child of 45. Let me update the number here to 67. And I'll connect that as the
08:15right child. Okay. And now we're done adding 67. Any questions? I'm just kidding. That was rude.
08:29Just know that my heart is with you. If you're asking questions, send me a comment in the comments.
08:35So now I'm going to move over to the 10 here. Again, we look at the 67, the 10 belongs
08:41on the left.
08:42So we kind of go to the left. We look at the 12, the 10 belongs on the left of
08:48the 12 because it's
08:48less than 12. So that is an available slot. That's an available child pointer. So I'm going to say
08:55the 10 is going to be the left child of the 12 node. Maybe I'll stick it all the way
09:00over there.
09:00Let's see. Is there anything less than 10 in there? Nope. Okay. So we'll be good. We have
09:06enough space on the screen. So change that to a 10. Do the connecting line. So the 10 is now
09:13the left
09:13child. Whoops. The left child of the 12 node. And now we're ready to add the next node.
09:23Okay. So now the 43 is the next one we want to add. One more time. We look at the
09:3073 node. The root
09:31node is occupied. So we have to go to the left because 43 is less. So, oops, that's a line.
09:37So
09:37now we look at the 12 node. Is 43 greater than or less than the 12? It's greater than. So
09:42that means
09:42we go down to the right. But the 45 is there. So we have to make another decision. 43 is
09:48less than 45.
09:49So we go to the left. That means this 43 is going to be the left child of 45. And
09:55again, don't try to
09:56make the tree pretty or better. Just let the nodes fall wherever they're supposed to fall according to
10:03the rules of less than or greater than. So now we got the, whoops, I forgot to change that to
10:09a 43.
10:11The 43 right there. And we are now ready to add another node. So I'm going to like erase this
10:17stuff
10:17here. And I want to move the arrow to the 11. Now, once again, we're looking for the root node.
10:24It's already occupied. We say that 11 is supposed to go on the left because it's less than.
10:30We look at the 12. It's occupied. So we have to go to the left because 11 is less than
10:3412.
10:35We go to the 10. And that's also occupied. So we have to make another decision. Is 11 greater than
10:41less than 10. It's greater than. So that's why the 11 goes on the right side of the 10. So
10:46I'm
10:46going to duplicate this over here. Notice how I'm trying to keep same ranked children or same depth
10:53children physically at the same level. It's a lot easier to debug your diagrams if you do things this
10:58way. Notice also, as I mentioned in a previous video, that every left descendant of a node should
11:06be physically on the left side in my diagram and every right descendant should be physically on the
11:11right side. That just makes the diagram way easier to debug. What do I mean by this? Look at 73's
11:17left
11:18descendants, its left subtree. They're all physically on the left. Look at the 12 node, all of its right
11:23descendants or its right subtree. They're all physically on the right. So if you follow that rule,
11:28it's just way easier to debug. I think I forgot to update that number from 43 to 11. So I'm
11:33going to do
11:34that now. And we are ready to add the next number, the 99. So I'm going to do this. We're
11:41looking at
11:4299. So first we start off by looking at the root node. It's 73, occupied. 99 belongs on the right
11:48side.
11:49So now we bounce to the right side and we look at the 98. Whoops, whoops, whoops. We look at
11:55the 98.
11:57That's occupied. So we make another decision. The 99 belongs on the right side of 98. That slot is
12:02available. So now we can say that the 99 node is supposed to be a right child of 99. Sorry,
12:12sorry. The 99
12:14is the right child of the 98 node. I'm getting a little confused. Okay, so I'm going to do a
12:20little
12:20connecting line there. And we're ready to add the final value into our tree.
12:29So I'm going to do, let's see. Oh, oh, I accidentally erased the arrow. Oh, there it is.
12:35We can add the 32 next. And if we look at the 73, it's occupied. 32 belongs on the left.
12:42So then we just kind of like follow down to the left here. We look at the 12. 32 belongs
12:47on the
12:47right of 12. So we follow down to the right. 32 belongs on the left of 45. So we follow
12:52down to
12:52the left. 32 belongs on the left of 43. And so we will make 32 the left child of the
12:5843
12:59node. So I'm going to like select this real fast. We go down a full rank. And I'm going
13:04to try to split the difference between 12 and 43 here, just to make the diagram easier to
13:08debug. Okay, so then I'm going to do. It's looking a little gross, but at least we're finished.
13:17Um, I have to update that 11 to be the 32. And now we're done building our tree.
13:26Okay. So some things to point out real fast, notice how the tree is lopsided. And if you,
13:31you know, look at various parts of the tree, you might be frustrated. Why didn't we put the 98
13:35over there? Why didn't we put the right? Just it's fine. As long as we follow the rules of building
13:40a
13:41binary search tree, then this is the valid tree that we would have built. Of course, later on,
13:45you'll learn techniques to make the tree a little bit better looking a little bit faster.
13:49But right now we're just building a tree with no optimizations, no self balancing,
13:54no anything like that. This is our binary search tree. Now, real fast, let's debug the tree.
14:01If we were to take all of the, you know, all the numbers that we added and sort them,
14:07then that should be the numbers we see from left to right. This is another good argument for why we
14:11should draw the diagram in this way. Again, like same depth nodes. Let me just draw the depths real
14:18fast, just to kind of illustrate the point a little bit. Same depth nodes should be on the
14:21same y coordinate or the same horizontal plane. Notice how 73 is the root node. And then 12 with
14:2898 have a depth of one. And then 10, 45 and 99 have a depth of two. And then 11,
14:3543 and 67 have a depth of
14:36three. And then 32 has a depth of four. So the deepest node we can find has a depth of
14:41four.
14:41That's the 32 node, which means the height of the tree. Um, height is four, sorry, five. The height is
14:50always the deepest nodes depth plus one, um, or the number of nodes you would have to touch as you
14:56found
14:56your way down to the deepest node. For example, if we wanted to get to that 32, we would touch
15:01one,
15:01two, three, four, five nodes. So the height of this tree is five. Okay. Um, let's debug the order
15:11of our numbers because this is kind of easy to get wrong. So from left to right, we should see
15:16a
15:16sorted list. So let me just, uh, do little markings here to indicate that I'm seeing increasing or at
15:22least non-decreasing numbers. If our tree supported duplicates, uh, then it would be non-decreasing.
15:28But since we don't allow duplicates, it should be increasing or an ascending list. So I'm going to
15:34do, uh, the 10. And as we look towards the right, we should see increasing numbers. So we got the
15:3910
15:39there and then we got the 11 there. And then we got the 12 there, 32, 43, 45, 67. So
15:47far, so good.
15:48It's all increasing. 73 increases, 98 increases and 99 increases. So from left to right, it was basically
15:55a sorted list, which is what we want. So we've created a valid ordering for the tree. Now, maybe
16:00just think about all the rules of a binary search tree to make sure we did that right too. So
16:05is this
16:05a graph? Yeah. Is it a connected graph? Yeah. Is it a tree? You know, no cycles in the graph?
16:11Yeah.
16:12Is it a root of tree? Yeah. The 73 root node, uh, is the common ancestor of all other nodes.
16:17We have
16:17one node that's common to the whole tree in terms of ancestry. Um, does any node have more than two
16:25children? No, none of the nodes have more than two children. Um, they've all got zero or one or two
16:31children. And then the numbers are in order. And therefore this is a valid binary search tree.
16:37So in other videos, I'm going to talk about the time complexity and, and like, you know,
16:42how fast it is to do certain operations or how imbalanced a tree may be and how that might
16:46affect things. But, uh, just so you know, this is not a perfect binary search tree. You can tell
16:52because it's a little lopsided. Um, we calculated the height as five and let's see where the heck is
16:58that calculator? I thought I had a calculator on here. Oh no. Oh, there it is. If we calculated the
17:05height as five and you could probably imagine, and we'll talk about searching in a future video,
17:10like how do you search in a way that makes the tree super, super fast? Well, we certainly built
17:14the tree in a way that makes it super, super fast. We just have to get to searching later.
17:18But, uh, if we search properly through a properly built binary search tree, then at most it should
17:25only take us height number of examinations, uh, to find our way to any piece of data or to determine
17:32that a piece of data doesn't exist. For example, um, I could say that the, uh, time complexity is O
17:39and we'll do this in other videos of, uh, H. It's always O of H, no matter what the tree
17:45looks
17:45like, no matter how lopsided it is. And what is H here? Five. That just basically is saying
17:51in the worst case scenario, I would have to touch five nodes to reach the very bottom of the tree
17:56and determine that, um, a value didn't exist, uh, or, you know, find a value at the very bottom
18:01of the tree. So the worst case scenario, touch five nodes. So it's O of H. If we, if we
18:06plug this
18:06into a calculator, a perfect binary search tree should be, uh, log base two. So if we did
18:13log base two of N where N is the number of nodes, uh, Oh, how many nodes do we have?
18:19Shoot.
18:20One, two, three, four, five, six, seven, eight, nine, 10. I think one, two, three, four, five,
18:24six, seven, eight, nine, 10. Yeah. Log base two of 10. Notice how the number here says, well,
18:29it should take like somewhat close to three, uh, examinations at most for examinations, but we just
18:36said, it's going to take up to five examinations. So notice how there's a little bit of a divergence
18:40between the real speed of the tree. It might take up to five examinations and log base two,
18:48uh, which would be a perfect binary search tree. So the more lopsided a tree gets,
18:51the slower it actually becomes. And we'll deal with that in future videos. We'll learn how to like
18:57detect that and balance that and so forth. But so we've built a binary search tree. It's definitely
19:04valid if, if not, you know, like super, super fast. And I think that's the end of this video.
19:09Thank you so much for watching. I hope you learned a little bit of stuff and had a little bit
19:12of fun.
19:13Uh, in the next video, I think I'm just going to build another tree for you. Uh, so we can
19:17get a
19:17second practice in. Okay. Future videos also are going to include searching and deleting nodes and,
19:25uh, and modifying existing nodes and just a whole bunch of other stuff. Then eventually we'll do
19:29self balancing trees. I'll see you later. Hey everybody. Thanks for watching this video again
19:38from the bottom of my heart. I really appreciate it. I do hope you did learn something and have
19:42some fun. Uh, if you could do me a please, a small little favor, could you please subscribe and follow
19:49this channel or these videos or whatever it is you do on the current social media website that you're
19:54looking at right now? Um, it would really mean the world to me and it'll help make more videos
19:58and grow this community. So we'll be able to do more videos, longer videos, better videos,
20:03or just, I'll be able to keep making videos in general. So please do, do me a kindness and, uh,
20:09and subscribe. You know, sometimes I'm sleeping in the middle of the night and I just wake up because
20:13I know somebody subscribed or followed. It just wakes me up and I get filled with joy. That's exactly
20:18what happens every single time. So you could do it as a nice favor to me or you could, you
20:22could troll me if you
20:23want to just wake me up in the middle of the night, just subscribe and then I'll, I'll just wake
20:26up.
20:27Uh, I promise that's what will happen. Also, uh, if you look at the middle of the screen right now,
20:32you should see a QR code, which you can scan in order to go to the website, which I think
20:36is also
20:36named somewhere at the bottom of this video. And it'll take you to my main website where you can just
20:41kind of like see all the videos I published and the services and tutorials and things that I offer
20:46and all that good stuff. And, uh, if you have a suggestion for, uh, uh, clarifications or errata,
20:55or just future videos that you want to see, please leave a comment. Or if you just want to say,
20:59Hey, what's up, what's going on? You know, just send me a comment, whatever. I also wake up for those
21:03in the middle of the night. I get, I wake up in a cold sweat and I'm like, it would
21:08really,
21:09it really mean the world to me. I would really appreciate it. So again, thank you so much for watching
21:13this
21:13video and, um, enjoy the cool music as, as I fade into the darkness, which is coming for us all.
Comments