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
=-=-=-=-=-=-=-=-=
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
Hello there! Let’s practice constructing a binary search tree from scratch.
In my previous video, we actually did this already, and in other previous videos we defined
what is a binary search tree and some terminology and stuff like that, but I thought it would
be nice to have two practice videos up. I’m willing to put more up if people want to make
comments about more trees that they want to see inserted. For now, I’m just going to say
we will add the following sequence of numbers. So this is a little diagram from the last time we
did this. Let me just, oh, I’m supposed to make that full screen so it can be bigger. Whoops.
Let me go ahead and add a new slide here. And then I’m going to do,
Okay, so we’re going to try to add the following sequence of numbers.
Like I said in my other video, don’t try to make the tree prettier.
Don’t get mad if a number looks like it’s too far to the left or something.
Just follow the normal rules of letting a node drop wherever it is supposed to drop
according to the rules of building a binary search tree.
So the first thing that I’m going to do is maybe draw a little arrow here.
I’m going to do like a pink arrow to indicate, you know,
You know, well, maybe I’ll do like a red one to indicate which number we’re actually trying to add at the moment.
So it’s going to be the 88 first.
Let’s see, we’ll put that right there.
And then now let’s say that the 88 is going to drop into our tree somewhere.
First question we have to ask ourselves is do we have a root node?
We don’t have a root node, which means the number we’re trying to add should be the root node.
And that’s it.
So I’m going to draw like a little circle here, a little node.
and I’m going to stick the number 88 inside of it we’re using integer t types
if you recall the last videos these nodes are supposed to be able to hold
almost any data type that you want they don’t have to be numbers but I’m just
going to use numbers for the sake of this example because it’s easier so I’m
going to say this is our root node it’s at the very top of the tree and we’re
done adding 88 and that’s it next step we’re going to add the 21 so I’m just
forward a little bit here and the 21 same question do we have a root node we currently do so that
means we can’t actually put the 21 there so we have to make a decision does the 21 belong on the
left or the right of the 88 the 21 is less than 88 which means it belongs on the left side so i’m
just going to duplicate this and try to make a pretty diagram by sort of splitting the difference
in terms of the empty space on the left between the edge of the screen and the existing root node
and make sure that it goes down, you know, a full rank, you know, at least the full height of a node,
maybe a little bit more, but you want to keep all same depth nodes on the same Y coordinate.
It’s just easier to debug your diagrams that way.
This one’s actually probably going to get messy. I might have to readjust this a few times.
I think I recalled these were, these might’ve been bad numbers. I can’t remember.
Okay. So the 21 is going to be the left child of the 88 because it belongs on the left side.
So I’m just going to do my little connecting line here.
connecting line here now 21 has a parent of 88 and 88 has a left child of 21 and we’re done adding
the 21 so i’m going to move the arrow to the three we’re now trying to add the three node
again we look at the root node we say okay that’s occupied so we can’t use that does three belong on
the left or the right of the 88 well it’s less than 88 so it belongs on the left the left child
again, does the three belong on the left or the right of the 21? It belongs on the left
because it’s less than 21 and the left child of 21 is currently doesn’t exist. It’s null.
So that means the three is going to be the new left child of the 21 node. Maybe just put it
like right there, put the three there. And then I’m going to do the connecting line in your code.
You can imagine that the left child pointer of the 21 node has now been set. So it’s pointing
been set so it’s pointing to the brand new node we just made for the three and then inside of the
three node its parent pointer is pointing to the 21 node okay so we’re done adding the three we
move on to the six same thing that we did before we look at the root node uh the six belongs on
the left so i’m gonna say go to the left the 21 node is it’s there it’s occupied so we have to
left of 21 because it’s less than 21 we go down to the left then we look at the three that’s also
occupied does the six belong on the left or right of three it belongs on the right side of three
because it’s greater than three so that means the sixth node is going to be the right child
of three again try to split the difference these diagrams get ugly fast i really
i don’t i don’t want to rearrange the topology but i’m probably gonna have to
I think I’m like crashing out here.
Oh, no.
Okay.
Nope.
Okay.
Let me try one more time.
These lines are killing me.
Okay.
I’m just going to update the three to a six and leave a little gap on that line.
It’s fine.
Now we’re ready to try to add the 72 node.
We have a little relief here because this is not like a smaller and smaller number that we’re dealing with.
So, well, we just look at the root node.
72 belongs on the left side so I’m going to hop to the left here we then look at
the 21 72 belongs on the right side because it’s greater than 21 so that
means 72 is going to be the right child of 21 so I’m just going to select this
make a duplicate try to keep the three and the six at the same you know y
coordinate because they’re on the same descendancy rank they’re at the same
you know generation whatever you want to call it so I’m going to put the 72 on
And then I’m going to do our connecting line, indicating that both nodes now have pointers that refer to each other.
Okay, we’re done adding the 72.
I’m going to move this to the right a little bit.
And then, oops, get rid of that little dot.
Now we’re ready to add the 34.
So the 34, we look at the 88 node occupied.
We go left.
We look at the 21 node.
34 belongs on the right side of 21.
of 21 so then we look at the 72 34 belongs on the left side of 72 so that means 34 is going to be
the left child of 72 so I’m going to select one of these nodes and duplicate it and say that
you have a left child of 72 now and it’s going to be the 34 node do my pointer connection real fast
I haven’t been duplicating the pages. Okay. So, uh, I guess that’s just for me.
We’ll move on to adding the 11 node.
So we add the 11 node by looking at the root node first.
11 belongs on the left side. We then look at the 21,
11 belongs on the left of 21. Go to the left here. We look at the three,
11 belongs on the right of the three. We go to the right,
11 belongs on the right of the six node.
This is definitely a gross graph at this point.
at this point. So I’m going to duplicate this node here and try to split the difference between
the six and the 21 in terms of like the free space. So I’m just going to drag this down a
little bit there and say that 11 goes as the new right child of the six node. So
just do that. This is a gross diagram. I might want to redraw this later.
Now we’re ready to try to add the one node.
the one again we look at the root node of the tree and it’s occupied so we can’t put it there
we go to the left we go to the left again and the one belongs on the left of the three nodes so we
have a little bit more room there so that’s good i’m gonna copy this node and make it the new left
child of the three i’m gonna like say that our one is right there and then i’m gonna do the connecting line
okay all right we’re done adding the one now I’m gonna add the 90 node oh this is
gonna be nice and easy because the 90 definitely belongs on the right side of
the 80 node whoops what happened okay sorry for making that noise I’m gonna
duplicate this node here and make it the right child of the 88 node so let’s see
kind of even there. So we’re going to put 90 right there. And then I’m going to do a connecting line
in blue. Now we’re done adding the 90.
So then we’re going to add the 65. 65 belongs on the left of the 88 node.
So we’re kind of in left territory now. It’s kind of sucky again.
And bounce down to the left. 66 belongs on the right side of the 21 node. So we look at the 72.
look at the 72 it belongs on the left of the 72 we go there it belongs on the right of the 34 so we
go right here as the new right child and the diagram kind of sucks at this point it’s a little
cramped but i’m going to try my best to split the difference between the 34 and the 32 visually to
make a nice easy to debug graph so maybe like somewhere around there put 66 then i’m going to
So the 66 is now the right child of 34.
Okay, next number that we’re going to add is my computer’s crashing.
Hello?
What happened?
There we go.
Okay.
So we’re ready to add the 55.
Oh, God.
Okay, let me see what’s going to happen here.
This is awful.
is awful i usually say you have to space these out enough so that none of these overlap but
they’re about to overlap okay we’ll do go to the left because 55 is less than 88 go to the right
because 55 is greater than 21 go to the left because it’s less than 72 go to the right because
it’s greater than 34 then go to the left again because it’s less than 66 i hate this i hate this
between 34 and 66, just to try to make it easier to debug.
This is almost, I’m almost stretched
to my mental limit right now.
So I’m gonna make the left child pointer here
and the new node we just added was 55.
Whoops, yeah, 55.
Okay, my God.
Let me just duplicate this one more time
and get rid of those pink arrows.
arrows let’s add the 17 next 17 right here um so once again we look at the root node it’s occupied
go to the left because it’s less than we look at the 21 we go left because it’s less than 21
we go to the right because it’s greater than three we look at the six we go to the right
because it’s greater than six we go to the right because it’s greater than 11.
So a super cramped diagram.
I’m in hell.
I’m just going to move this slightly to the right because this is just awful.
And I’m going to try to make sure again that same depth nodes are at the same Y coordinate.
Let me fix that number real fast before I forget.
And put it as a 17.
And then do my connecting line.
Like that.
Okay.
I’m losing it.
The, uh, whoops, the 23, where is this going to go?
Is it 23?
Um, Hmm.
Hmm.
Oh, well, it’s going to be like left child of the 34 probably.
Okay.
Let me just, uh, look at the root node.
Okay.
23 belongs on the left of that.
Look at the 21, 23 belongs on the right of that.
Cause it’s greater than 21.
Look at the 72.
It belongs on the left.
it belongs on the left look at the 34 belongs on the left and then that’s going to be the new left
child okay so I’m going to duplicate one of these nodes and it’s going to be the new left child of
the 34 node that is awful but I guess we barely have enough room let me change that to a 23 and
then I’ll add my connecting line okay and now we’re ready to add the final value in our tree
to be? It’s going to be like left child of 11 maybe. So we look at the root node. Whoops,
forgot to move that arrow. We look at the root node. We can’t put it there. Nine belongs on the
left side of the root. So we go like that. Nine belongs on the left side of the 21. Oh, did I just
guess something wrong? No, no, no. I think I’m okay. Go to the left side of that. We look at
right side of three we look at the six nine belongs on the right side of the six we look at
the eleven nine belongs on the left side of eleven because it’s less than eleven so I’m just going to
duplicate this and it’s going to end up being the left side whoops nope that’s wrong hang on a second
let me oh come on man let me get this down it’s going to be the left child of eleven not the left
there and the diagram is a little messed up maybe I should try to rearrange this in a second
it the topology is correct but it’s harder to debug because you can see that one of the right
descendants of the six node is actually physically on its left side and that just makes it extra hard
to debug but for now we’ll say that we’re done adding stuff into the tree so maybe I can kind
I’m not going to change the actual topology.
I’m just going to like, you know, redraw this in a slightly nicer way.
So I can probably take this whole subtree and move it over to the left a little bit to make it a little cleaner.
Which will give me some room to move this subtree a little bit over to the right.
Am I still wearing my microphone? Yeah.
And then it’s a little bit cleaner.
Then I just have to redraw this line.
Whoops.
oops yeah just have to redraw this line and now i think we’re following the rules that i talked
about before where a good diagram has all the left descendants physically on the left side of
a given node so let’s see the six has everything on the right and everything i think we’re okay
i’m going to duplicate this real fast and now let’s verify that our tree is actually correct
So I said this in the last video when we built a tree, but you basically want to take like the input data set here and sort it.
And whatever sorted list you end up with, that’s what you should see when you scan your eyes from left to right.
Again, this is another good argument for drawing the diagram in a really good way.
All left descendants are physically on the left. All right descendants are physically on the right.
So another way that I could do this, besides I don’t really want to sort this list right now,
Just scan from left to right and make sure that I see increasing numbers
Or if you’ve decided to make a tree that supports duplicates, make sure that you see non-decreasing numbers
But I’m looking for an ascending list
Okay, so I’m gonna just like do little hashes here
One is the lowest number. That’s good. Then if I go to the right just a little bit
I see a three go to the right a little bit. I see a six that’s still increasing then I see a nine and then I see an 11
still been increasing go to the right a little bit more it’s a 21 go to the right a little bit more
it’s a 23 then it’s a 34 then it’s a 55 then it’s a 66 then it’s a 72 so far everything’s been
increasing and then from 72 to 88 and from 88 to 90. so the ordering of the numbers are correct
let me just make sure i actually have a binary search tree by the definition of a bst first it
crazy lines going off in some direction or like different symbols this is a
connected graph meaning I could probably find well I definitely could find a path
from any node to any other node if I just you know trace the edges so can the
9 find its way to the 90 yeah if we just kind of like go you know up this way and
follow the edges up to the 88 and then back down to the 90 so every single node
could do that it could find every single other node on the graph which means this
every single other node on the graph which means this is a connected graph so that’s good the next
thing is now that we have a connected graph do we have a tree so check for cycles uh can any start
node find its way back to itself in a path that does not repeat edges i don’t see that anywhere
in the tree so i think we have a valid tree let me get rid of that real fast so for example uh
Could we find a path that goes away from the 9 node and then comes back without repeating any edges?
I cannot because as soon as we go out to the 11,
later on we would have to use that same edge to come back down to the 9 and that would be repeating an edge.
So we just kind of check that for every single node.
We can’t find a cycle anywhere in this entire graph.
So this is an acyclic graph.
Okay, that means it’s a tree.
Is this a rooted tree?
ancestor to all other nodes and it’s that 88 node that’s the root node of the
entire tree every single node in the tree can say that 88 is its greatest
ancestor there’s no you know same leveled nodes at the very very very top okay so
this is a rooted tree now is it a binary tree yeah we look at every single node
and we can see that none of the nodes have more than two children they’ve all
this is a binary tree. And then when we, you know, we verified the numbers a second ago,
that means this is a binary search tree. So it satisfies all the properties of a binary search
tree. It doesn’t look very good. It’s kind of wonky, but it is valid. Remember this,
you know, a binary search tree just by itself is not a self-balancing tree,
which means you, you, you need to like not inject your human feelings into the tree while you’re
building it and start rearranging it to make it prettier. It wouldn’t be a valid binary search
if you tried to add special rules when you were creating it.
I don’t know.
If you imagine that maybe you, the human,
were changing the input data,
then I guess that’s valid.
But don’t imagine that the tree
is changing the data as you add it.
Anyway, so how fast is this tree?
Remember we said in a previous video
that a perfect binary search tree,
meaning perfectly balanced on every single node,
would be a log time tree.
It would be really, really fast to add and search
to add and search and even remove but this tree is definitely lopsided so this
is not a log tree the time complexity of a binary search tree actually is not
really log because the tree could just grow in any direction so in the worst
case scenario if you add the worst possible data you’d end up with a linear
time tree self balancing trees will be log time trees because they always
rearrange themselves to make sure that they’re balanced to a certain extent but
But, you know, as a binary search tree scales, it could just get slower and slower and slower.
So we wouldn’t be able to say that BSTs, binary search trees in general are log time.
We could pull up a calculator though and we could say, well, you know, what’s the height of this particular tree?
Let me just look at the depths real fast here.
What’s the height of this tree?
So the root node has a depth of zero and then one and then two and then three and then four.
drawing your tree in a nice pretty way where all the ranks are the same physically.
We just take the deepest node and we add one to it and we say that’s the height.
So the height of this tree is six.
Another way of looking at it is if we wanted to touch one of the deepest nodes,
how many nodes would we have to touch as we travel down through the tree?
So how many nodes would we have to touch to find, you know, the nine or the 17 or the 55?
one node the 88 two and let’s go to the left three four five six we’d have to touch six nodes
to get to the deepest node so that’s why we’re saying that’s another way that we’re justifying
that we say the height is six so the height of this tree is six which means in the worst case
scenario if we needed to search this tree again we’ll talk about actually searching in another
video but for now i can just promise you that if we were going to search this tree we could do it
going to search this tree we could do it in at most six uh examinations so even though we have
a lot of nodes here how many nodes do we actually have let me just double check this we have n
is equal to one two three four five six seven eight nine ten eleven twelve thirteen fourteen
we have fourteen nodes but at most we’d have to examine six nodes because this is a binary search
tree so it’s a lot faster than scanning the whole tree in linear time but it could be a lot faster
It could be a lot faster if the tree was better balanced.
That’s a topic for another day.
So for example, if we wanted to search for the number 55, let’s say we were just going
to search for 55, you know, we’d look at the 88.
Basically searching is pretty much the same as adding a node.
You just kind of go find where the node would belong.
And then if it’s there, then you found it.
And if not, then it’s not in there.
55 belongs on the left of 88, belongs on the right of 21, it belongs on the left of 72.
belongs on the left of 72, belongs on the right of 34, belongs on the left of 66, and there we
found it. Notice how we only did one, two, three, four, five, six examinations. So I’m going to talk
about big O and time complexities in another video, but long story short, the time complexity
of this particular tree, or actually any binary search tree, is always going to be O of H, no
imbalanced or perfectly balanced O of H so in the worst case scenario since H is 6 we’re going to have to touch H or 6 nodes
To search or add something or whatever if the tree was perfect. It would look more like log time. Let’s pull up that calculator real fast
Where the heck is my calculator? I think I like got sidetracked
so if I pull up a calculator here
and I typed in
log base 2 it’s base 2 because we only allow two children per node at most log
base 2 of the number of nodes in the tree so log base 2 of 14 if we get the
answer to that it says 3.8 which means the calculator is telling us that in a
log time tree we should not have to examine more than four nodes in order to
search the tree or add a brand new node but this is not a log tree because it is
totally imbalanced it’s kind of wonky it’s not it’s not perfect so it’s telling us in a perfect
tree we’d have to touch four nodes only but we clearly know we might have to touch six nodes in
the worst case so that i’m just trying to bring to your attention that the more imbalanced the tree is
the further its uh performance drifts away from log time which is a great argument
I think this is pretty much everything I wanted to talk about today.
I’m going to take a break and like, you know, eat some cookies and stuff.
But in a future video, we’re going to talk about inserting.
No, we already just did that literally right now.
We’re going to talk about searching through the tree.
We’re going to talk about removing nodes from the tree.
We’re going to talk about linear trees.
We’re going to talk about all the time complexities.
And then eventually we’ll move on to self-balancing trees.
on to self-balancing trees. So I hope you had fun watching this video. I hope you learned a little
bit of stuff and I’ll see you at a later date in time. I’m outie. Patowdy. Note to self, edit out
Patowdy. Hey everybody, thanks for watching this video again from the bottom of my heart. I really
hope you did learn something and have some fun if you could do me a please a small little favor
could you please subscribe and follow this channel or these videos or whatever it is you do on the
current social media website that you’re looking at right now it would really mean the world to me
and it’ll help make more videos and grow this community so we’ll be able to do more videos
longer videos better videos or just i’ll be able to keep making videos in general so please
and subscribe. You know, sometimes I’m sleeping in the middle of the night and I just wake up
because I know somebody subscribed or followed. It just wakes me up and I get filled with joy.
That’s exactly what happens every single time. So you could do it as a nice favor to me or you
could, you could troll me if you want to just wake me up in the middle of the night, just subscribe
and then I’ll, I’ll just wake up. I promise that’s what will happen. Also, uh, if you look at the
middle of the screen right now, you should see a QR code, which you can scan in order to go to the
we’re at the bottom of this video and it’ll take you to my main website where you can just kind of
like see all the videos i published and the services and tutorials and things that i offer
and all that good stuff and uh if you have a suggestion for uh uh clarifications or errata
or just future videos that you want to see please leave a comment or if you just want to say hey
what’s up what’s going on you know just send me a comment whatever i also wake up for those in the
wake up in a cold sweat and i’m like it would really it really mean the world to me i would
really appreciate it so again thank you so much for watching this video and um enjoy the cool music
as as i fade into the darkness which is coming for us all
Thank you.
