- 3 minutes ago
In this hands-on tutorial, we build a binary search tree (BST) from scratch by inserting numbers one by one: 88, 21, 3, 6, 72, 34, 11, 1, 90, 65, 55, 17, 23, and 9. Watch as each node finds its correct position following BST rules, with clear explanations of left and right child decisions, parent pointers, and why the tree ends up looking a bit wonky but is still valid.
We cover the full insertion process, verify the tree is a proper BST by checking inorder traversal (sorted order), confirm it's a connected acyclic rooted binary tree, and discuss tree height, time complexity (O(h) where h=6 for this tree), and why self-balancing trees matter for better performance.
Great practice for computer science students, programmers learning data structures, or anyone prepping for coding interviews. No fancy animations - just real step-by-step drawing and reasoning.
If you want more BST practice videos or specific insertion sequences, drop a comment below!
00:00 Introduction to BST Practice
00:35 Insertion Sequence Overview
00:59 Rules for Building BST
01:30 Insert 88 as Root
02:20 Continue building the tree from input data
13:04 Finish building the tree
14:56 Clean Up Diagram
15:24 Verify Inorder Traversal
16:48 Confirm Tree Properties
19:23 Tree Height and Time Complexity
22:01 Search Example for 55
23:09 Log Time vs Actual Height
24:21 Conclusion and Future Topics
binary search tree, BST insertion, binary search tree tutorial, build BST from scratch, data structures, algorithms, BST insertion step by step, binary tree, tree height, time complexity BST, coding interview prep, computer science, inorder traversal, self balancing trees
=-=-=-=-=-=-=-=-=
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
We cover the full insertion process, verify the tree is a proper BST by checking inorder traversal (sorted order), confirm it's a connected acyclic rooted binary tree, and discuss tree height, time complexity (O(h) where h=6 for this tree), and why self-balancing trees matter for better performance.
Great practice for computer science students, programmers learning data structures, or anyone prepping for coding interviews. No fancy animations - just real step-by-step drawing and reasoning.
If you want more BST practice videos or specific insertion sequences, drop a comment below!
00:00 Introduction to BST Practice
00:35 Insertion Sequence Overview
00:59 Rules for Building BST
01:30 Insert 88 as Root
02:20 Continue building the tree from input data
13:04 Finish building the tree
14:56 Clean Up Diagram
15:24 Verify Inorder Traversal
16:48 Confirm Tree Properties
19:23 Tree Height and Time Complexity
22:01 Search Example for 55
23:09 Log Time vs Actual Height
24:21 Conclusion and Future Topics
binary search tree, BST insertion, binary search tree tutorial, build BST from scratch, data structures, algorithms, BST insertion step by step, binary tree, tree height, time complexity BST, coding interview prep, computer science, inorder traversal, self balancing trees
=-=-=-=-=-=-=-=-=
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
Category
đŸ¤–
TechTranscript
00:01Hello there! Let's practice constructing a binary search tree from scratch.
00:13In my previous video, we actually did this already, and in other previous videos we defined what is a binary
00:19search tree,
00:20and some terminology and stuff like that, but I thought it would be nice to have two practice videos up.
00:24I'm willing to put more up if people want to make some comments about more trees that they want to
00:30see inserted.
00:33For now, I'm just going to say we will add the following sequence of numbers.
00:37So this is a little diagram from the last time we did this.
00:40Let me just, oh, I'm supposed to make that whole screen so it can be bigger.
00:45Let me go ahead and add a new slide here, and then I'm going to do, is that going to
00:53work?
00:54Yes, that's the sequence I wanted.
00:56Okay, so we're going to try to add the following sequence of numbers.
00:59Like I said in my other video, don't try to make the tree prettier.
01:03Don't get mad if a number looks like it's too far to the left or something.
01:06Just follow the normal rules of letting a node drop wherever it is supposed to drop,
01:11according to the rules of building a binary search tree.
01:15So the first thing that I'm going to do is maybe draw a little arrow here.
01:18I'm going to do like a pink arrow to indicate, you know, well, maybe I'll do like a red one
01:26to indicate which number we're actually trying to add at the moment.
01:30So it's going to be the 88 first.
01:33Let's see, we'll put that right there.
01:35And then, now let's say that the 88 is going to drop into our tree somewhere.
01:40First question we have to ask ourselves is, do we have a root node?
01:43We don't have a root node, which means the number we're trying to add should be the root node, and
01:48that's it.
01:48So I'm going to draw like a little circle here, a little node, and I'm going to stick the number
01:5388 inside of it.
01:55We're using integer T types.
01:57If you recall the last videos, these nodes are supposed to be able to hold almost any data type that
02:02you want.
02:03They don't have to be numbers, but I'm just going to use numbers for the sake of this example because
02:08it's easier.
02:09So I'm going to say this is our root node.
02:11It's at the very top of the tree, and we're done adding 88, and that's it.
02:17Next step, we're going to add the 21.
02:19So I'm just going to go forward a little bit here.
02:21And the 21, same question, do we have a root node?
02:24We currently do, so that means we can't actually put the 21 there.
02:29So we have to make a decision.
02:30Does the 21 belong on the left or the right of the 88?
02:34The 21 is less than 88, which means it belongs on the left side.
02:37So I'm just going to duplicate this and try to make a pretty diagram by sort of splitting the difference
02:43in terms of the empty space
02:44on the left between the edge of the screen and the existing root node and make sure that it goes
02:49down, you know, a full rank,
02:51you know, at least the full height of a node, maybe a little bit more.
02:55But you want to keep all same depth nodes on the same Y coordinate.
02:59It's just easier to debug your diagrams that way.
03:02This one's actually probably going to get messy.
03:04I might have to readjust this a few times.
03:05I think I recall these were, these might have been bad numbers.
03:09I can't remember.
03:10Okay, so the 21 is going to be the left child of the 88 because it belongs on the left
03:14side.
03:14So I'm just going to do my little connecting line here.
03:17Now 21 has a parent of 88 and 88 has a left child of 21.
03:21And we're done adding the 21.
03:23So I'm going to move the arrow to the 3.
03:26We're now trying to add the 3 node.
03:29Again, we look at the root node.
03:31We say, okay, that's occupied.
03:32So we can't use that.
03:34Does 3 belong on the left or the right of the 88?
03:36Well, it's less than 88.
03:37So it belongs on the left.
03:40The left child is occupied though.
03:42So we have to make the same decision again.
03:44Does the 3 belong on the left or the right of the 21?
03:47It belongs on the left because it's less than 21.
03:50And the left child of 21 is currently doesn't exist.
03:53It's null.
03:53So that means the 3 is going to be the new left child of the 21 node.
03:58Maybe just put it like right there, put the 3 there.
04:03And then I'm going to do the connecting line in your code.
04:07You can imagine that the left child pointer of the 21 node has now been set.
04:12So it's pointing to the brand new node we just made for the 3.
04:15And then inside of the 3 node, its parent pointer is pointing to the 21 node.
04:21Okay.
04:21So we're done adding the 3.
04:23We move on to the 6.
04:26Same thing that we did before.
04:28We look at the root node.
04:29The 6 belongs on the left.
04:31So I'm going to say go to the left.
04:34The 21 node is there.
04:36It's occupied.
04:37So we have to go left or right.
04:386 is supposed to be on the left of 21 because it's less than 21.
04:41We go down to the left then.
04:43We look at the 3.
04:44That's also occupied.
04:45Does the 6 belong on the left or right of 3?
04:47It belongs on the right side of 3 because it's greater than 3.
04:50So that means the 6 node is going to be the right child of 3.
04:55Again, try to split the difference.
04:56These diagrams get ugly fast.
04:59I really...
05:01I don't want to rearrange the topology, but I'm probably going to have to.
05:06Okay.
05:07I think I'm like crashing out here.
05:10Oh, no.
05:11No.
05:12Okay.
05:13Nope.
05:13Okay.
05:14Let me try one more time.
05:15Ugh.
05:17These lines are killing me.
05:18Okay.
05:19I'm just going to update the 3 to a 6 and leave a little gap on that line.
05:22It's fine.
05:24Now we're ready to try to add the 72 node.
05:27We have a little relief here because this is like not like a smaller and smaller, you
05:31know, number that we're dealing with.
05:32So, well, we just look at the root node.
05:3672 belongs on the left side.
05:37So I'm going to hop to the left here.
05:39We then look at the 21.
05:4172 belongs on the right side because it's greater than 21.
05:43So that means 72 is going to be the right child of 21.
05:47So I'm just going to select this, make a duplicate.
05:49Try to keep the 3 and the 6 at the same, you know, Y coordinate because they're on the
05:54same, uh, descendancy rank.
05:57They're at the same, you know, generation, whatever you want to call it.
06:01Um, so I'm going to put the 72 on the right side and then I'm going to do our
06:05connecting line indicating that both nodes now have pointers that refer to each other.
06:12Okay.
06:12We're done adding the 72.
06:13I'm going to move this to the right a little bit and then, uh, get rid of that little dot.
06:21Now we're ready to add the 34.
06:25So the 34, uh, we look at the 88 node occupied.
06:28We go left.
06:29We look at the 21 node.
06:3034 belongs on the right side of 21.
06:32So then we look at the 72.
06:3534 belongs on the left side of 72.
06:37So that means 34 is going to be the left child of 72.
06:41So I'm going to select one of these nodes and duplicate it and say that, uh, you have
06:47a left child of 72 now, and it's going to be the 34 node.
06:52Do my pointer connection real fast.
06:56Then we're ready to move on.
06:59Oh man, I haven't been duplicating the pages.
07:02Okay.
07:03So, uh, I guess that's just for me.
07:05We'll move on to adding the 11 node.
07:08So we add the 11 node by looking at the root node.
07:11First 11 belongs on the left side.
07:13We then look at the 21 11 belongs on the left of 21.
07:18Go to the left here.
07:19We look at the three 11 belongs on the right of the three.
07:22We go to the right 11 belongs on the right of the six node.
07:26This is definitely a gross graph at this point.
07:28So I'm going to duplicate this node here and try to split the difference between the six
07:33and the 21 in terms of like the free space.
07:35So I'm just going to drag this down a little bit there and say that 11 goes as the new
07:41right
07:41child of the six node.
07:43So just do that.
07:46This is a gross diagram.
07:48I might want to redraw this later.
07:51Uh, now we're ready to try to add the one node.
07:55So the one, again, we look at the root node of the tree and it's occupied.
08:01So we can't put it there.
08:02We go to the left, we go to the left again, and the one belongs on the left of the
08:07three nodes.
08:07So we have a little bit more room there.
08:09So that's good.
08:10I'm going to copy this node and make it the new left child of the three.
08:15I'm going to like say that, uh, our one is right there.
08:20And then I'm going to do the connecting line.
08:24Okay.
08:25All right.
08:27We're done adding the one.
08:30Now I'm going to add the 90 node.
08:32Oh, this is going to be nice and easy because the 90 definitely belongs on the right side of
08:36the 80 node.
08:38Oh, whoops.
08:39What happened?
08:41Okay.
08:43Sorry for making that noise.
08:45Uh, I'm going to duplicate this, uh, node here and make it the right child of the 88 node.
08:50So let's see, keep it, uh, kind of even there.
08:53So we're going to put 90 right there.
08:55And then I'm going to do a connecting line in blue.
09:01Now we're done adding the 90.
09:05So then, uh, we're going to add the 65, 65 belongs on the left of the 88 node.
09:10So we're kind of in left territory.
09:12Now it's kind of sucky again.
09:14Um, bounce down to the left.
09:1766 belongs on the right side of the 21 node.
09:19So we look at the 72.
09:21It belongs on the left of the 72.
09:23We go there.
09:24It belongs on the right of the 34.
09:25So we go, uh, right here as the new right child.
09:28Eh, the diagram kind of sucks at this point.
09:31It's a little cramped, but I'm going to try my best to split the difference between the
09:3434 and the 32 visually to make a nice, easy to debug a graph.
09:40So maybe like somewhere around there, but 66, then I'm going to do my connecting line.
09:49So the 66 is now the right child of 34.
09:54Okay.
09:55Uh, next number that we're going to add is my computer's crashing.
10:01Hello.
10:03What happened?
10:05There we go.
10:06Okay.
10:07So we're ready to add the 55.
10:10Oh God.
10:12Okay.
10:12Let me see what's going to happen here.
10:15This is awful.
10:16I usually say you have to space these out enough so that none of these overlap, but they're
10:19about to overlap.
10:21Okay.
10:22We'll do go to the left because 55 is less than 88.
10:26Go to the right because 55 is greater than 21.
10:28Go to the left because it's less than 72.
10:31Go to the right because it's greater than 34.
10:33Then go to the left again because it's less than 66.
10:38I hate this.
10:40I hate this.
10:40Okay.
10:42Uh, I'm going to split the difference between 34 and 66 just to try to make it easier to
10:47debug.
10:49Uh, this is almost, I'm almost stretched to my mental limit right now.
10:54So I'm going to make the left child pointer here and, uh, the new node we just added was
10:5955.
11:00Whoops.
11:02Yeah.
11:0255.
11:05Okay.
11:07My God.
11:08Let me just duplicate this one more time.
11:10Um, and, uh, get rid of those pink arrows.
11:12Let's add the 17 next 17 right here.
11:18Um, so once again, we look at the root node.
11:22It's occupied, go to the left because it's less than we look at the 21.
11:28We go left because it's less than 21.
11:31Uh, we go to the right because it's greater than three.
11:33We look at the six.
11:34We go to the right because it's greater than six.
11:37We go to the right because it's greater than 11.
11:39So a super cramped diagram.
11:43I'm in hell.
11:44I'm just going to move this slightly to the right because this is just awful.
11:48And I'm going to try to make sure again, that same depth nodes are at the same Y coordinate.
11:52Uh, let me fix that number real fast before I forget and put it as a 17 and then do
11:58my connecting line like that.
12:01Okay.
12:05I'm losing it.
12:06Now let's add the, uh, whoops, the 23.
12:12Where's this going to go?
12:15Is it 23?
12:17Um, Hmm.
12:19Hmm.
12:19Oh, well, it's going to be like left child of the 34 probably.
12:24Okay.
12:25Let me just, uh, look at the root node.
12:28Okay.
12:2923 belongs on the left of that.
12:30Look at the 21, 23 belongs on the right of that.
12:33Cause it's greater than 21.
12:34Look at the 72.
12:36It belongs on the left.
12:37Look at the 34 belongs on the left.
12:39And then that's going to be the new left child.
12:42Okay.
12:42So I'm going to duplicate one of these nodes and it's going to be the new left child of the
12:4534 node.
12:47That is awful, but I guess we barely have enough room.
12:49Let me change that to a 23 and then I'll add my connecting line.
12:56Okay.
12:57And now we're ready to add the final value in our tree, which is going to be the nine.
13:02Where the heck is that going to be?
13:04Uh, it's going to be like left child of 11, maybe.
13:09Oh, okay.
13:12So we look at the root node.
13:13Whoops.
13:14Forgot to move that arrow.
13:16We look at the root node.
13:17Uh, we can't put it there.
13:19Nine belongs on the left side of the root.
13:21So we go like that.
13:23Nine belongs on the left side of the 21.
13:25Oh, did I just guess something wrong?
13:27No, no, no.
13:27I think I'm okay.
13:28Go to the left side of that.
13:30We look at the three.
13:31Nine belongs on the right side of three.
13:32We look at the six.
13:34Nine belongs on the right side of the six.
13:35We look at the 11.
13:37Nine belongs on the left side of 11 because it's less than 11.
13:40So I'm just going to duplicate this and it's going to end up being the left side.
13:46Whoops.
13:46Nope.
13:46That's wrong.
13:48Hang on a second.
13:49Come on, man.
13:51Let me get this down.
13:52It's going to be the left child of 11, not the left child of, uh, six.
13:57Okay.
13:57So we put the nine right there and, uh, the diagram's a little messed up.
14:04Maybe I should try to rearrange this in a second.
14:07It, uh, the topology is correct, but it's harder to debug because you can see that, uh,
14:13one of the right descendants of the six node is actually physically on its left side.
14:17And that just makes it extra hard to debug.
14:20But for now, we'll say that we're done, uh, adding stuff into the tree.
14:23So maybe I can kind of reorganize this just a little bit.
14:28I'm not going to change the actual topology.
14:31I'm just going to like, you know, redraw this in a slightly nicer way.
14:35So I can probably take this whole subtree and move it over to the left a little bit to make
14:41it a little cleaner,
14:43which will give me some room to move this subtree a little bit over to the right.
14:48Am I still wearing my microphone?
14:49Yeah.
14:50Uh, and then it's a little bit cleaner.
14:52Then I just have to redraw this line.
14:55Whoops.
14:58Yeah.
14:58I just have to redraw this line.
15:00And now I think we're following the rules that I talked about before,
15:05where a good diagram has all left descendants physically on the left side of a given node.
15:13So let's see the six has everything on the right and everything.
15:16Okay.
15:17I think we're okay.
15:18I'm going to duplicate this real fast.
15:20And now let's verify that our tree is actually correct.
15:23So I said this in the last video when we built the tree, but you basically want to take like
15:27the input data set here and sort it.
15:30And, uh, whatever sorted lists you end up with, that's what you should see when you scan your eyes from
15:36left to right.
15:36Again, this is another good argument for drawing the diagram in a really good way.
15:40All left descendants are physically on the left.
15:42All right descendants are physically on the right.
15:46So another way that I could do this besides, I don't, I don't really want to sort this list right
15:50now,
15:50but another way I could do it is just scan from left to right and make sure that I see
15:54increasing numbers.
15:55Or if you've decided to make a tree that supports duplicates, make sure that you see non-decreasing numbers,
16:01but I'm looking for an ascending list.
16:03Okay.
16:04So I'm going to just like do little hashes here.
16:07Uh, one is the lowest number.
16:08That's good.
16:09Then if I go to the right, just a little bit, I see a three go to the right a
16:13little bit.
16:13I see a six that's still increasing.
16:15Then I see a nine and then I see an 11.
16:18Uh, and then I see a 17.
16:20It's still been increasing.
16:21Go to the right a little bit more.
16:22It's a 21.
16:23Go to the right a little bit more.
16:24It's a 23.
16:26Then it's a 34.
16:27Then it's a 55.
16:28Then it's a 66.
16:30Then it's a 72.
16:31So far, everything's been increasing.
16:32And then from 72 to 88 and from 88 to 90.
16:36So the ordering of the numbers are correct.
16:39Let me just make sure I actually have a binary search tree by the definition of a BST.
16:44Uh, first it needs to be a graph.
16:45Okay.
16:46We just have like nodes and edges.
16:47We don't have any crazy lines, uh, going off in some direction or like different symbols.
16:53This is a connected graph, meaning I could probably find, well, I definitely could find a path,
16:58uh, from any node to any other node if I just, you know, trace the edges.
17:01So can the nine find its way to the 90?
17:04Yeah.
17:05If we just kind of like go, you know, up this way and follow the edges up to the 88
17:11and then back down to the 90.
17:12So every single node could do that.
17:15It could find every single other node on the graph, which means this is a connected graph.
17:18So that's good.
17:20The next thing is now that we have a connected graph, do we have a tree?
17:24So check for cycles.
17:26Uh, can any start node find its way back to itself in a path that does not repeat edges?
17:32I don't see that anywhere in the tree.
17:34So I think we have a valid tree.
17:36Let me get rid of that real fast.
17:39So for example, uh, if we started at the nine node, could we find a path that goes away from
17:46the nine node and then comes back without repeating any edges?
17:49I cannot, because as soon as we go out to the 11, later on, we would have to use that
17:54same edge to come back down to the nine and that would be repeating an edge.
17:59Uh, so we just kind of check that for every single node.
18:01We can't find a cycle anywhere in this entire graph.
18:04So this is an acyclic graph.
18:07Okay.
18:07That means it's a tree.
18:08Uh, is this a rooted tree?
18:10Well, yeah, there is one common ancestor to all other nodes and it's that 88 node.
18:15That's the root node of the entire tree.
18:17Every single node in the tree can say that 88 is its greatest ancestor.
18:22There's no, you know, same leveled, uh, nodes at the very, very, very top.
18:26Okay.
18:26So this is a rooted tree.
18:29Uh, now is it a binary tree?
18:31Yeah.
18:31We look at every single node and we can see that none of the nodes have more than two children.
18:35They've all got zero or one or two children.
18:39So this is a binary tree.
18:41And then when we, you know, we verified the numbers a second ago, that means this is a binary search
18:46tree.
18:46So it satisfies all the properties of a binary search tree.
18:50Uh, it doesn't look very good.
18:51It's kind of wonky, but it is valid.
18:53Remember this, you know, a binary search tree just by itself is not a self-balancing tree,
18:58which means you, you, you need to like not inject your human feelings into the tree while you're building it
19:03and start rearranging it to make it prettier.
19:05Uh, it wouldn't be a valid binary search tree if you tried to add special rules, uh, when you were
19:10creating it.
19:13I don't know if you imagine that maybe you, the human were changing the input data, then I guess that's
19:18valid.
19:18Uh, but, uh, don't imagine that the tree is changing the data as you add it anyway.
19:24So how fast is this tree?
19:25Remember we said in a previous video that a perfect binary search tree, meaning perfectly balanced on every single node,
19:33uh, would be a log time tree.
19:35It would be really, really fast to add and search and even remove, but this tree is definitely lopsided.
19:40So this is not a log tree.
19:43The time complexity of a binary search tree actually is not really log because the tree could just grow in
19:48any direction.
19:48So in the worst case scenario, if you add the worst possible data, you'd end up with a linear time
19:54tree.
19:54Um, self-balancing trees will be log time trees because they always rearrange themselves to make sure, uh, that they're
20:01balanced, uh, to a certain extent.
20:04But, uh, you know, as a binary search tree scales, it could just get slower and slower and slower.
20:10So we wouldn't be able to say that BSTs binary search trees in general are log time.
20:14We could pull up a calculator though.
20:16And we could say, well, you know, what's the height of this particular tree?
20:19Let me just look at the depths real fast here.
20:22What's the height of this tree?
20:24So the root node has a depth of zero and then one and then two and then three and then
20:29four.
20:30This is another argument for drawing your tree in a nice pretty way where all the ranks are the same
20:36physically.
20:37We just take the deepest node and we add one to it and we say that's the height.
20:41So the height of this tree is six.
20:44Another way of looking at it is if we wanted to touch one of the deepest nodes,
20:48how many nodes would we have to touch as we traveled down through the tree?
20:53So, uh, how many nodes would we have to touch to find, you know, the nine or the 17 or
20:58the 55?
20:58We'd have to touch, you know, one node, the 88, two, and let's go to the left, three, four, five,
21:06six.
21:06We'd have to touch six nodes to get to the deepest node.
21:09Uh, so that's why we're saying that's another way that we're justifying that we say the height is six.
21:15So the height of this tree is six, which means in the worst case scenario, if we needed to search
21:20this tree,
21:21again, we'll talk about actually searching, uh, in another video.
21:25But for now I can just promise you that if we were going to search this tree,
21:29we could do it in at most six, uh, examinations.
21:33So even though we have a lot of nodes here, how many nodes do we actually have?
21:37Let me just double check this.
21:38We have N is equal to 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14.
21:45We have 14 nodes, but at most we'd have to examine six nodes because this is a binary search tree.
21:52So it's a lot faster than scanning the whole tree in linear time, but it could be a lot faster
21:57if the tree was better balanced.
21:58That's a topic for another, another day.
22:01So for example, um, if we wanted to search for the number 55, let's say we were just going to
22:07search for 55.
22:08Uh, you know, we'd look at the 88 basically searching is pretty much the same as adding a node.
22:13You just kind of go find where the node would belong.
22:16And then if it's there, then you found it.
22:17And if not, then it's not in there.
22:20Uh, 55 belongs on the left of 88, belongs on the right of 21.
22:24It belongs on the left of 72, belongs on the right of 34, belongs on the left of 66.
22:30And there we found it.
22:31Notice how we only did one, two, three, four, five, six examinations.
22:36So, um, I'm going to talk about big O, uh, and time complexities in another video,
22:41but long story short, the time complexity of this particular tree, or actually any binary search tree,
22:46is always going to be O of H, no matter how bad or good the tree is.
22:51If it's imbalanced or perfectly balanced.
22:53O of H.
22:54So in the worst case scenario, since H is six, we're going to have to touch H or six nodes
23:00to search or add something or whatever.
23:03If the tree was perfect, it would look more like log time.
23:06Let's pull up that calculator real fast.
23:08Uh, where the heck is my calculator?
23:10Uh, I think I like got sidetracked.
23:14So if I pull up a calculator here and I typed in, uh, log base two,
23:21it's base two because we only allow two children per node at most.
23:27Log base two of the number of nodes in the tree.
23:29So log base two of 14, we get the answer to that.
23:32It says 3.8, which means the calculator is telling us that in a log time tree,
23:37we should not have to examine more than four nodes in order to search the tree or add a brand
23:42new node.
23:43Um, but this is not a log tree because it is totally, it's not totally imbalanced.
23:49It's kind of wonky.
23:50It's not, it's not perfect.
23:52So it's telling us in a perfect tree, we'd have to touch four nodes only,
23:55but we clearly know we might have to touch six nodes in the worst case.
24:00So that I'm just trying to bring to your attention that the more imbalanced the tree is,
24:04the further it's, uh, performance drifts away from log time,
24:10which is a great argument, uh, for self-balancing trees eventually.
24:17Um, I think this is pretty much everything I wanted to talk about today.
24:21I'm going to take a break and like, you know, eat some cookies and stuff.
24:24But, uh, in a future video, we're going to talk about, uh, inserting.
24:29No, we already just did that literally right now.
24:32We're going to talk about searching through the tree.
24:34We're going to talk about removing nodes from the tree.
24:37Uh, we're going to talk about, uh, linear trees.
24:40We're going to talk about all the time complexities,
24:42and then eventually we'll move on to self-balancing trees.
24:46Um, so I hope you had fun, uh, watching this video.
24:50I hope you learned a little bit of stuff and, uh, I'll see you at a later date and time.
24:55I'm outie.
24:57But howdy.
25:03Note to self, edit out Patowdy.
25:06Hey everybody.
25:08Thanks for watching this video again from the bottom of my heart.
25:10I really appreciate it.
25:11I do hope you did learn something and have some fun.
25:14Uh, if you could do me a please, a small little favor,
25:17could you please subscribe and follow this channel or these videos
25:21or whatever it is you do on the current social media website
25:24that you're looking at right now.
25:25Um, it would really mean the world to me
25:27and it'll help make more videos and grow this community.
25:30So we'll be able to do more videos, longer videos, better videos,
25:33or just I'll be able to keep making videos in general.
25:36So please do, do me a kindness and, uh, and subscribe.
25:40You know, sometimes I'm sleeping in the middle of the night
25:43and I just wake up because I know somebody subscribed or followed.
25:46It just wakes me up and I get filled with joy.
25:48That's exactly what happens every single time.
25:50So you could do it as a nice favor to me or you could,
25:52you could troll me if you want to just wake me up in the middle of the night,
25:55just subscribe and then I'll, I'll just wake up.
25:57Uh, I promise that's what will happen.
26:00Also, uh, if you look at the middle of the screen right now,
26:02you should see a QR code, which you can scan in order to go to the website,
26:06which I think is also named somewhere at the bottom of this video.
26:09And it'll take you to my main website where you can just kind of like,
26:12see all the videos I published and the services and tutorials and things that I offer
26:16and all that good stuff.
26:18And, uh, if you have a suggestion for, uh, uh, clarifications or errata,
26:25or just future videos that you want to see, please leave a comment.
26:28Or if you just want to say, Hey, what's up, what's going on?
26:31You know, just send me a comment, whatever.
26:33I also wake up for those in the middle of the night.
26:35I get, I wake up in a cold sweat and I'm like,
26:38it would really, it would really mean the world to me.
26:41I would really appreciate it.
26:42So again, thank you so much for watching this video and, um,
26:46enjoy the cool music as, as I fade into the darkness,
26:51which is coming for us all.
27:16So.
27:18Oh.
27:22Oh.
27:25Oh.
27:31Oh.
Comments