Building a Binary Search Tree - Insertion Tutorial - video Dailymotion

Neural Lantern

In this hands-on video we build a binary search tree by inserting numbers one by one: 73, 98, 12, 45, 67, 10, 43, 11, 99, and 32. Watch exactly how each node finds its place following BST rules with no rearranging allowed.  We discuss why the tree becomes lopsided, calculate its height, and verify the in-order traversal is sorted. Great practice for anyone learning binary search trees.  Next videos will cover searching and deleting nodes.  If you're studying data structures, build along with me!  00:00 Introduction to Building a Binary Search Tree 00:14 Plan for Inserting Numbers 00:30 First Node Becomes Root 02:26 Begin inserting from data set 12:29 Final insertion from data set 13:26 Final Tree Overview 13:29 Tree is Lopsided 14:00 Drawing Depths and Levels 14:50 Calculating Tree Height 15:08 Verifying Sorted Order 16:00 Confirming BST Properties 16:48 Time Complexity and Height 18:59 No Self-Balancing 19:07 End of Video and Thanks  binary search tree, BST insertion, build binary search tree, binary search tree tutorial, data structures, BST from scratch, insert into binary search tree, binary tree insertion, computer science tutorial, algorithms, BST height, BST depth, in order traversal, binary search tree example, data structures and algorithms  =-=-=-=-=-=-=-=-=  Thanks for watching!  Find us on other social media here: - https://www.NeuralLantern.com/social - Twitter / X: https://x.com/NeuralLantern - Rumble: https://rumble.com/c/c-3696939 - BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt - Daily Motion: https://www.dailymotion.com/neurallantern - Minds: https://www.minds.com/neurallantern/ - Odysee: https://odysee.com/@NeuralLantern:5  Please show your support!  - Buy me a coffee: https://ko-fi.com/neurallantern  - Subscribe + Sharing on Social Media - Leave a comment or suggestion - Subscribe to the Blog: https://www.NeuralLantern.com - Watch the main "pinned" video of this channel for offers and extras

Transcript

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.

Building a Binary Search Tree - Insertion Tutorial

Category

Transcript

Comments

Recommended