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
=-=-=-=-=-=-=-=-=
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
hey there let’s build a binary search tree together if you’ve seen my previous videos
you understand now how to define a binary search tree meaning what are the rules
that you have to like adhere to if you want your thing to be a binary search tree
also terminology we’re in previous videos so in this video we’re just going to take a bunch of
random numbers and we’re just going to start dropping them into our tree and see how the
tree builds itself out we have to build our tree in a specific way if it’s going to be valid we’re
uh valid we’re not going to rearrange our tree and try to make it super pretty this is going to be
like a real binary search tree it might not be pretty but it’ll be real let’s see if i can find
those numbers that i was going to set up okay so for this particular video i think i’m going to do
two videos i want to build a binary search tree using the following numbers they’re not special
not not perfect but what I mean to say when I say inserting these numbers is one by one we’ll look
at each number and we’ll drop it in the tree and we’ll see where it falls according to binary
search tree rules of insertion then we’ll just go to the next number and then the next and the next
when we’re done we should have a tree and if you follow along at home and you use the right rules
to build your tree then if we use the same sequence of numbers to build the tree we should
they won’t suddenly be different they’re deterministic okay so the first thing that
we should try to understand is uh when we want to insert a node the 73 node right here the first
thing we should ask ourselves is do we actually have a root node for our binary search tree yet
right now the answer is no this is just a blank tree there’s nothing in it which means that first
number is going to be the root node you might be tempted to say no that’s a sucky root node let’s
do something else well i don’t know i mean you just have to let the numbers fall where they’re
going to fall just because a number seems to suck as a root node doesn’t mean it’s not going to be
the root node if it’s the first thing you added it’s going to be the root node don’t try to change
it or you’re going to mess you’re going to end up with topology that doesn’t match whatever system
or person is trying to grade your work or evaluate your work so we have no root node that means the
node of the entire tree we’re now done with 73 i’m going to duplicate this slide real fast
and we’ll say now it’s time to try to add the 98 you know what i can i think i can do better than
that arrow i can make a nice cute arrow with this program i’m going to do this can i like yeah
hang on one more one more try nice okay so now let’s add the 98 node
the first thing we have to ask is do we have a root node uh yes we can’t actually put the 98 there
we now have to make a decision uh if you recall in my previous videos the lesser values go on the
left and the greater values go on the right uh in in these trees which we’re not going to support
duplicate values with if you wanted to support duplicate values you could do something like
less than or equal to would be on the left and greater than on the right there’s a bunch of
other ways you can do it but i’m just going to say no duplicate values in our trees so we look at the
So we look at the 73 node and we ask, you know, is that where our 98 is going to go?
It can’t go there because 73 exists.
Now we have to ask the question, does 98 belong on the left side or the right side of the 73?
Well, because 98 is greater than 73, it belongs on the right side, which means I’m going to duplicate this node over here.
And I’m going to try to draw this well, which means basically splitting the difference in terms of the empty space.
empty space and trying to keep the same rank as we go down one level of
descendancy or like one generation down at a time.
So the next time I go down a level,
let’s say I do a left child in the future,
it should be at the same level as the new node I just added.
So I did a duplicate and I forgot to change the number.
And then I’m going to do a line to connect the 73 and the 98.
98 so now the 73 has a right child which is 98 the 98 has a parent which is 73 and we’re done
adding the 98 we have to just move on to the next number okay so i’m going to move on to the 12
again we look at the root node it’s occupied we cannot put the 12 right there on the 73 we have
to make a decision do we go to the left or the right of the 73 12 is less than 73 so it belongs
is to jump to the left side. Notice how the left side there’s no child on the left that means that’s
where the new node is going to go so I’m just going to like select this duplicate it real fast
maybe stick it on the same vertical coordinate and then also try to split the difference on
the screen just to make it look pretty. I’m going to update that 98 so that it is now the 12.
child 12 and then we’re done adding the 12. Okay, no problem so far. We then are ready to try to
add the 45. Maybe I should squish this a little bit. Nope, that looks gross. No, it’s okay.
We’ll do that. We’re going to add the 45. Again, we look at the root node. It already exists,
so we can’t put the 45 there. Instead, we will just kind of decide does the 45 belong on the
Okay, well, belongs on the left because it’s less than 73.
So that means I’m now going to make a little decision.
I’m going to jump down to the left.
If you’re in some code, you’re following the left child pointer down.
But notice how the left child pointer or the left child, it already exists.
So we can’t actually put 45 right there.
We have to make another decision.
Does 45 belong on the left or the right of the 12?
Well, it’s greater than 12.
So it belongs on the right side of 12.
So I’m going to highlight this and duplicate it.
and duplicate it. I guess I’ll just do it that way. Then I’m going to update that number
with 45 and then I’m going to connect the 12 and the 45 with the line. So now 45 is the right child
of 12 and 12 is the parent of 45. It’s at this point that a lot of people start to get frustrated
with me and they say, well, how come, how come the 12 is like all the way to the left and the 45 is
45 is like didn’t become like you know a level higher because it kind of seems like it’s closer
to 73 shouldn’t the 12 be hanging off the left child of the 45 no no no no don’t rearrange the
nodes as you’re building the tree just let the numbers let the nodes fall wherever they’re
supposed to go another tip is if you’re building a tree that has other data types as as the t types
inside of the nodes as the template types inside of the nodes for example right now I’m just using
type is int, at least in my mind, if you wanted to put dinosaur objects in the tree, all you’d
have to do is make sure that your code for your dinosaur class for your dinosaur object
had its inequality operators implemented, you know, less than, greater than, and then the tree
would still know where to put all the objects. So you could make any kind of custom object you want
and they would all fall in their correct places in the tree as long as the operators actually
just as a side note. Okay, so now we’re ready to add the next item. So I’m going to erase this
stuff here, and I’m going to move the arrow from the 45 to the 67. So now we’re going to try to
add the 67. We look at the root node, it’s occupied. We should go to the left because 67
is less than 73. We look at the 12, that’s occupied. So we go left or right. We should go
to the right because 67 is greater than 12. So we look at the 45. Again, it’s occupied. There’s a
a node there so we have to make another decision do we go to the left or to the right well 67 is
greater than 45 so it goes on the right side so i’m going to duplicate this off to the right side
and down a rank and we’ll call that the right child of 45. let me update the number here
to 67 and i’ll connect that as the right child okay
Any questions? I’m just kidding. That was rude. Just know that my heart is with you if you’re
asking questions. Send me a comment in the comments. So now I’m going to move over to the 10 here.
Again, we look at the 67. The 10 belongs on the left. So we kind of go to the left.
We look at the 12. The 10 belongs on the left of the 12 because it’s less than 12.
available slot that’s an available child pointer so I’m going to say the 10 is going to be the
left child of the 12 node maybe I’ll stick it all the way over there let’s see is there anything
less than 10 in there nope okay so we’ll be good we have enough space on the screen
so change that to a 10 do the connecting line so the 10 is now the left child
whoops the left child of the 12 node and now we’re ready to add the next node
node. Okay. So now the 43 is the next one we want to add. One more time, we look at the 73 node,
the root node is occupied. So we have to go to the left because 43 is less. So oops, that’s a line.
So now we look at the 12 node is 43 greater than or less than the 12. It’s greater than so that
means we go down to the right. But the 45 is there. So we have to make another decision. 43 is less
43 is less than 45 so we go to the left that means this 43 is going to be the left child of 45.
And again don’t try to make the tree pretty or better just let the nodes fall wherever they’re
supposed to fall according to the rules of less than or greater than. So now we got the uh whoops
I forgot to change that to a 43. The 43 right there and we are now ready to add another node
So I’m going to like erase this stuff here and I want to move the arrow to the 11.
Now once again, we’re looking for the root node.
It’s already occupied.
We say that 11 is supposed to go on the left because it’s less than.
We look at the 12.
It’s occupied.
So we have to go to the left because 11 is less than 12.
We go to the 10 and that’s also occupied.
So we have to make another decision.
Is 11 greater than or less than 10?
It’s greater than.
why the 11 goes on the right side of the 10. So I’m going to duplicate this over here. Notice how
I’m trying to keep same ranked children or same depth children physically at the same level. It’s
a lot easier to debug your diagrams if you do things this way. Notice also, as I mentioned in
a previous video, that every left descendant of a node should be physically on the left side in my
diagram and every right descendant should be physically on the right side. That just makes
right side that just makes the diagram way easier to debug what do I mean by this look at 73’s left
descendants its left subtree they’re all physically on the left look at the 12 node all of its right
descendants or its right subtree they’re all physically on the right so you if you follow
that rule it’s just way easier to debug I think I forgot to update that number from 43 to 11 so
I’m going to do that now and we are ready to add the next number the 99 so I’m going to do this
So I’m going to do this. We’re looking at 99.
So first we start off by looking at the root node.
It’s 73, occupied. 99 belongs on the right side.
So now we bounce to the right side and we look at the 98.
Whoops, whoops, whoops. We look at the 98.
That’s occupied, so we make another decision.
The 99 belongs on the right side of 98. That slot is available.
So now we can say that the 99 node is supposed to be
a right child of 99.
Sorry, sorry.
The 99 is the right child of the 98 node.
I’m getting a little confused.
Okay, so I’m gonna do a little connecting line there.
And we’re ready to add the final value into our tree.
So I’m gonna do, let’s see.
Oh, oh, I accidentally erased the arrow.
Oh, there it is.
We can add the 32 next.
add the 32 next and if we look at the 73 it’s occupied 32 belongs on the left so then we just
kind of like follow down to the left here we look at the 12 32 belongs on the right of 12 so we
follow down to the right 32 belongs on the left of 45 so we follow down to the left 32 belongs on
the left of 43 and so we will make 32 the left child of the 43 node so I’m going to like select
this real fast we go down a full rank and I’m going to try to split the difference between 12
And I’m going to try to split the difference between 12 and 43 here just to make the diagram easier to debug.
Okay, so then I’m going to do…
It’s looking a little gross, but at least we’re finished.
I have to update that 11 to be the 32.
And now we’re done building our tree.
Okay, so some things to point out real fast.
Notice how the tree is lopsided.
to look at various parts of the tree you might be frustrated why didn’t we put the 98 over there
why didn’t we put the right just it’s fine as long as we follow the rules of building a binary search
tree then this is the valid tree that we would have built of course later on you’ll learn techniques
to make the tree a little bit better looking a little bit faster but right now we’re just building
a tree with no optimizations no self balancing no anything like that this is our binary search tree
tree if we were to take all of the uh you know all the numbers that we added and sort them
then that should be the numbers we see from left to right this is another good argument for why we
should draw the diagram in this way again like uh same depth nodes let me just draw the the depths
real fast just to kind of illustrate the point a little bit same depth nodes should be on the same
y coordinate or the same uh horizontal plane notice how 73 is the root node and then 12 with 98 have
with 98 have a depth of 1 and then 10 45 and 99 have a depth of 2 and then 11 43 and 67 have a
depth of 3 and then 32 has a depth of 4 so the deepest node we can find has a depth of 4 that’s
the 32 node which means the height of the tree um height is 4 sorry 5 the height is always the
deepest nodes depth plus 1 or the number of nodes you would have to touch as you found your way
you found your way down to the deepest node for example if we wanted to get to that 32 we would
touch one two three four five nodes so the height of this tree is five
okay um let’s debug the order of our numbers because this is kind of easy to get wrong
so from left to right we should see a sorted list so let me just uh do little markings here
to indicate that i’m seeing increasing or at least non-decreasing numbers
If our tree supported duplicates, then it would be non-decreasing.
But since we don’t allow duplicates, it should be increasing or an ascending list.
So I’m going to do the 10.
And as we look towards the right, we should see increasing numbers.
So we got the 10 there.
And then we got the 11 there.
And then we got the 12 there.
32, 43, 45, 67.
So far, so good.
It’s all increasing.
73 increases, 98 increases, and 99 increases.
and 99 increases. So from left to right, it was basically a sorted list, which is what we want.
So we’ve created a valid ordering for the tree. Now maybe just think about all the rules of a
binary search tree to make sure we did that right too. So is this a graph? Yeah. Is it a connected
graph? Yeah. Is it a tree? You know, no cycles in the graph? Yeah. Is it a rooted tree? Yeah. The 73
root node is the common ancestor of all other nodes. We have one node that’s common to the
in terms of ancestry um does any node have more than two children no none of the nodes have more
than two children um they’ve all got zero or one or two children and then the numbers are in order
and therefore this is a valid binary search tree so in other videos i’m going to talk about the
time complexity and and like you know how fast it is to do certain operations or how imbalanced a
just so you know this is not a perfect binary search tree you can tell because it’s a little
lopsided um we calculated the height as five and let’s see where the heck is that calculator i
thought i had a calculator on here oh no oh there it is if we calculated the height as five
you could probably imagine and we’ll talk about searching in a future video like how do you search
in a way that makes the tree super super fast well we certainly built the tree in a way that
makes it super super fast we just have to get to searching later but if we
search properly through a properly built binary search tree then at most it
should only take us height number of examinations to find our way to any
piece of data or to determine that a piece of data doesn’t exist for example
I could say that the time complexity is O and we’ll do this in other videos of
of h no matter what the tree looks like no matter how lopsided it is and what is h here five that
just basically is saying in the worst case scenario i would have to touch five nodes to reach the very
bottom of the tree and determine that a value didn’t exist or you know find a value at the very
bottom of the tree so the worst case scenario touch five nodes so it’s o of h if we if we plug
log base 2 so if we did log base 2 of n where n is the number of nodes uh oh how many nodes do we
have shoot one two three four five six seven eight nine ten i think one two three four five six seven
eight nine ten yeah log base two of ten notice how the number here says well it should take like
somewhat close to three uh examinations at most four examinations but we just said it’s going to
of a divergence between the real speed of the tree.
It might take up to five examinations and log base two,
which would be a perfect binary search tree.
So the more lopsided a tree gets, the slower it actually becomes.
And we’ll deal with that in future videos.
We’ll learn how to like detect that and balance that and so forth.
But so we’ve built a binary search tree.
It’s definitely valid if not, you know, like super, super fast.
And I think that’s the end of this video.
Thank you so much for watching.
I hope you learned a little bit of stuff and had a little bit of fun.
In the next video, I think I’m just going to build another tree for you so we can get
a second practice in.
Okay, future videos also are going to include searching and deleting nodes and modifying
existing nodes and just a whole bunch of other stuff.
Then eventually we’ll do self-balancing trees.
I’ll see you later.
Hey everybody.
Hey everybody!
Thanks for watching this video again from the bottom of my heart.
I really appreciate it.
I do 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
I’ll be able to keep making videos in general.
So please do me a kindness 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 troll me if you want to just wake me up in the middle of the night.
Just subscribe and then I’ll just wake up.
I promise that’s what will happen.
Also, if you look at the middle of the screen right now,
right now you should see a QR code which you can scan in order to go to the website which I think
is also named somewhere 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 if you have a suggestion for clarifications or
errata or just future videos that you want to see please leave a comment or if you just want to say
what’s going on you know just send me a comment whatever i also wake up for those in the middle
of the night i get i 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.
hey there let’s talk about uh
hello there hello there let’s build a binary search tree by just inserting a bunch of numbers
inserting a bunch of numbers and will follow the rules
