Clear step-by-step explanation of what defines a Binary Search Tree (BST). We build the definition rule-by-rule starting from graphs all the way to the BST ordering property (all left descendants, node, all right descendants). Great first video before learning insert, delete, search, and Big-O.
What is a Binary Search Tree? 00:00
Intro to Graphs and Nodes 00:42
Connected Graph Requirement 03:16
Acyclic Graph – Removing Cycles 04:54
Turning Graph into Tree 07:05
Establishing a Root 07:09
Adding Hierarchy and Levels 09:05
Single Common Ancestor 11:18
Binary Tree Definition 17:30
BST Ordering Property 17:39
Left Subtree Less Than Node 18:29
Fixing Invalid BST Example 20:26
Valid BST Final Check 21:24
In-Order Ascending Order 24:11
Video Summary and Next Steps 25:02
Thanks and Call to Action 25:30
=-=-=-=-=-=-=-=-=
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 talk about binary search trees specifically in this video I want to help you
define and identify what is a binary search tree all the rules that go into determining whether
or not something is a binary search tree so you can you can tell that you’re looking at one or
whether you’re not looking at one we’ll talk about some terminology but keep in mind I’m
going to save searching and sorting and like you know deleting and adding items and a whole bunch
extra stuff, especially the hard stuff for videos that’ll come right after this one.
For now, we’re just going to talk about what is a binary search tree.
So you can see on the screen right here, I hope that we have a binary search tree.
Let’s see.
Can you see that?
Yeah, I think you probably can.
Yeah, I think you can.
This is not drawn quite as well as I would like to draw ours.
I’ll tell you how to do that in a little while.
to do that in a little while but when you draw a tree in a really really nice pretty aligned way
it’s way easier to debug it’s way easier to tell that you’re looking at something that is sorted
and so forth anyway okay so first let’s start off with a graph so this is not a video about graphs
uh i guess i can probably expect that you already kind of know what a graph is at this point in time
and edges. So what do I mean by nodes? Well just imagine there’s like a little circle here
that contains some sort of data. If you know data structures already then
there would be a t-type sitting inside the node. We’ll just call the t-type an integer
and so for our nodes, for our trees, we’re just going to say that they hold integers even though
you know technically speaking in a binary search tree or a graph you could have all sorts of
Okay. So I’m just going to, you know, grab this and sort of like duplicate it and just duplicate it again.
I’m just going to make a bunch of duplicates. Something is definitely wonky about my setup right now.
I think I just upgraded the camera and the CPU is maxed out. I just upgraded the CPU on this computer too.
Oh well. Okay. So we aren’t going to support duplicate values in our binary search tree,
I’m going to say it doesn’t really matter for the graph. Later on, we’ll start making sure there’s
no duplicate data. For now, I think I can probably do that somewhat quickly. Let’s see. So a graph,
you know, for the for our purposes right now, a graph is just basically a collection of nodes and
edges. It could be empty. It could be just nodes. It couldn’t just be edges, it would have an edge
always has to have a node or two connected to it. So we just have like a bunch of nodes inside of
data values this is a valid graph but I’m going to draw some edges randomly here so we’re going
to do this it doesn’t really matter I’m just randomly drawing edges okay actually I should
probably do maybe like one that’s kind of separated okay so this is a graph this is not a binary search
tree so let’s add a bunch of rules let me just pull up my rules real fast here okay so what is
First we’ll start off with the graph like we have here and then we’ll say that the graph must be connected.
What is a connected graph? A connected graph is basically a graph where every single node can find every single other node
or find a path to every single other node only following along edges and only by respecting the direction of edges.
You can see this particular graph is undirected meaning the edges don’t really have a direction to them.
So that means we could travel along in any direction from node to node.
So just as a real quick, you know, I guess like tutorial, I’m going to say is 8 connected to every single other node?
Well, it can find a path to 12 and it can find a path to 33 and it can find a path to 76 and 45.
But it cannot find a path to 99, which means this is not a connected graph.
So that’s the first rule that we have to implement here.
We’re going to say this graph needs to be upgraded or modified so that it will be a connected graph.
start randomly adding edges until this is a connected graph I’m gonna do maybe
like an edge from 99 to 12 there and then now I think this is a connected
graph but let’s double check real fast so connected graph you know what I’m
gonna put graph connectedness in another video to keep this one short for now
check out my other videos if you would like to see whether or not a graph is
but long story short as I just said if every single node can find a path to
every single other node without you know skipping where there is no edge then
it’s connected okay so that’s the first thing the next thing that we need let me
just put the words connected up here we need a connected graph the next thing
that we need is we need an acyclic graph which basically means a graph with no
A cycle is, can you find a path in this graph that starts at one node and ends at the same node without repeating any edges?
So for example, if I was asking, you know, is 76 involved in any cycles?
Well, we could go from 76 to 33 and then 12.
And, you know, we could kind of take 8, 45, 12 again.
But by the time we turn around and try to get back to the 33, we’ve already crossed this edge twice.
so that means the 76 is not involved in any cycles because we cannot find our way back to 76
without repeating an edge so 76 is okay i’m just going to maybe put like a little check box here
and uh you can also tell that the 33 is not involved in any cycles because we go down to
the 76 and then come back up to 33 we already repeated an edge so that’s not valid same thing
again. Same thing for the 34, same thing for the 99. But if you look at the 12 here, we could
actually find a cycle. We could go from the 12 to the 8, and then from the 8 to the 45, and from the
45 to the 12. Now we’re back where we started. We’re at the 12 node again, and we did not repeat
any edges. So this is not a cyclic. This is a cyclic graph. It’s got a cycle. So that’s the
we want to make sure that our graph has no cycles. So, uh, the next rule I’m just going to say is,
is going to be satisfied by me removing some edges at random. So I don’t know, let’s get rid of, uh,
the eight to the 45 connection. See if that works. Um, let’s see. Well, wait a minute. What did I
just do? Something happened here. I just accidentally, oh, I erased too many edges
from the last slide. Okay. Let me add that one back in 33 to 76. That was supposed to be there.
33 to 76 that was supposed to be there.
So now we have an acyclic graph
and we can consider this graph a tree.
The next thing we need to do is add a hierarchy to this tree.
So this is gonna make more sense in a little bit
but for now I’m gonna say,
we’ll imagine a family tree kind of,
it’s not really exactly a family tree
but you know imagine there are parents
and children and grandchildren
and we’ll just try to like,
we’ll try to rank children according to
according to you know when they were born or or how many parents or children
they have you know their descendancy their lineage whatever you want to call
it so I think I’m just gonna maybe move the eight up a little bit so that it’s
on the same rank with the 12 and the 33 so I’m just gonna move these up a little
bit and then redo their connecting lines so I’m gonna do this and that and then
and then we’ll say that the 76 is still a child of the 33.
So I’ll just kind of move it over here.
Or sorry, we never said it was a child.
Now we’re saying it’s a child
because when you go from top to bottom,
imagine like a family tree,
we’ll say we have parents and children.
The children or the descendants are lower.
The ancestors or the parents or the grandparents are higher.
Maybe I want to put this 45 over on the left
so that it’s a child of the 8 node.
And maybe I’ll say that the 99 node
the 99 node is a child of the 12 node. Okay, so eventually this is going to look not exactly like
a family tree because usually in the family tree we have two parents that go to one or more children.
In this type of tree, in eventually our binary tree, we’re going to have one parent that has,
you know, children just by itself, like asexual reproduction. We’re pretending to be bacteria
What was that comedy skit a long time ago, Tiny Elvis?
And he was like, hey, see that protozoa over there?
The thing is huge.
Anyone?
No?
Okay.
So the next rule we need is we must have a rooted tree.
What is a rooted tree?
Actually, let me clean up the lineage real fast, the heritage.
I want to make nodes that have the same level with respect to their ancestors
respect to their ancestors to have the same physical y coordinate the same
physical level so notice how the 99 I just moved it down a little bit because
I wanted it to look like it’s the same you know number of generations lower
than the top row so like with aid it had a child 45 so that’s one level down 33
had a child that’s one level down that’s a 76 and the 12 also one level down
would have been 99 but the 99 was kind of too physically high this will help
will help you debug your binary trees in the future anyway so i’m just going to clean this up right now
and uh now that we have you know parent child relationships we need to look at the most common
ancestor in the whole entire tree or if there is one so notice how uh i guess i’m just kind of using
the word ancestor without explaining it so your ancestors are the people that you’re disappointing
or whatever it is, ancestors came before us, right?
Like my parents are my ancestors.
My grandparents are also my ancestors.
My great-grandparents are also my ancestors.
Going down in the family tree are your descendants.
You know, my children are my descendants.
My grandchildren are my descendants.
My great-grandchildren are my descendants and so forth.
So if you look at the number 34 here,
what is the greatest ancestor that it has?
Well, if you just go up and up and up
until you can’t go up anymore,
up until you can’t go up anymore it’s the 12th so that means the greatest ancestor of at least in
this tree of the 34 is the 12th the 45 the highest you can go is the 8 notice how 8 and 12 and 33 are
siblings there’s not really like a parent-child relationship they’re connected sideways we’ll
eventually get rid of the sideways connections for our binary search trees but for now we have
some siblings and so we actually have three different greatest ancestors in this tree we’ve
tree we’ve got 8 and 12 and 33 and that’s no good so the next rule that we need is we need
one common ancestor for every single other node in the entire tree so I’m going to duplicate this
slide right here and I’m going to say we need to clean this up so we got to choose 8 or 12 or 33
I don’t know I’m just going to maybe say that 8 and it’s 45 are children of the 12 so I’m just
line here arbitrarily so i’m gonna go like that notice how i’m trying to keep the 8 the 99 and
the 76 on the same y coordinate the same level now we have two uh you know greatest ancestors
we need to have only one so i think i’m probably going to say that the 33 and the 76 are going to
become children of the 12 node just for simplicity so i’m going to put this over here i’m going to
i’m gonna like move this over here this is a gross tree but we’ll fix it soon we’ll do that all right
okay okay
okay and then i have to get rid of that little sibling line and then i have to add another line
to say that 33 is a child of 12. okay so now we have a rooted tree what we had before was an
unrooted tree or just like not a rooted tree because there was no root there was no greatest
greatest common ancestor to the entire rest of the tree. But now we can say that 12 is the root
of the tree because it’s the ancestor for all other nodes. I guess even if 12 was by itself,
we could call it a root of tree. It just wouldn’t be a very good example. So I’m going to actually
get rid of the word acyclic here since we already handled that. And I’m going to do,
I’m going to say that 34’s greatest ancestor is 12, 99’s greatest ancestor is 12, 33’s greatest
all the nodes in the tree their greatest ancestor is 12 and it’s common to all of them so now we
have a rooted tree maybe I should type in my doomed I really hope the screen I really hope
the screen cast doesn’t freeze it probably will upgraded the CPU it’s 33 faster than it was before
board so i am still using an old cpu even though it’s new to me dang it i’m gonna have to spend
like 500 okay uh so the next rule is so we have a rooted tree and now let’s rearrange everything
hierarchically which we already kind of did so uh there’s not really much to do here except
we did hierarchical organization
we probably just need to move on to our next rule which is to say that
if our rooted tree is to become a binary tree
then each node in the entire tree
cannot have more than two children
every single node in the entire tree
can have zero or one or two children
if there are three or more anywhere in the entire tree
then it’s not a binary tree
so okay that means you know the 45 is okay
because it has no children
because it has no children. All the rows, all the leaves at the bottom are okay. All these nodes
over here are okay because they just have one child. But the 12 node, the root of the tree,
it’s got three children and that violates the rule. So now we need to rearrange this.
So I think I’m going to just move these numbers down here maybe. Whoops. Maybe move these nodes
descendants of the 33 node. So I’m going to do this.
Okay. So cool. Now we have a binary tree and now we need to rearrange the drawing a little bit.
This is not part of the definition, but this will make it easier to debug your trees. So what I want
to do is make it so that every left descendant of a node appears physically on that node’s left
every right descendant of a node should appear on its right side
or like further to the right on the x-coordinate
so sort of similar to you know like the y-coordinate ranking
but notice how the 12 its left child is 8 and its right child is 33
so that means all the nodes here on the left side you know that come underneath the 8
are left descendants or you could say that they are in the left subtree of the 12.
So, they’re okay because 8 is to the left of 12 and 45 is to the left of 12.
But notice how 33 is a right child of 12 and it’s part of the right subtree.
It’s part of the right descendancy, but it’s physically on the left of 12.
That’s going to be really bad because it’ll be harder to debug our trees later.
So, I’m just going to slide it over without rearranging the tree.
And I usually try to split the difference here.
and then their parent is kind of like physically in the middle that will also help you debug in
the future so i’m going to do this wrong let me get the blue i’m going to do this make sure that
my ranking is still okay not the best most neatest tree and so now i’m going to look at the eight
it’s left subtree or it’s left uh descendancy uh all of those nodes which is just the 45 are
it’s left child 76 is the only thing that’s on the left side in the left subtree so that’s all
right probably the 33 I think it’s still a little lopsided I probably could have you know dragged
it a little bit more to the right but I’m going to leave it so the 33 and the 76 are okay and then
the 99 is a right descendant or it’s part of the right subtree of the 33 so it should be on the
right side it is that’s good the 34 should be on the right side of the 33 because it’s it’s a it’s
It’s part of the right subtree of 33.
It’s part of the right descendancy.
And it should also be on the left side of the 99
because it’s part of the left subtree of the 99.
So, so far, this is okay.
This is not the best drawing.
So now we have a binary tree
and we have kind of drawn it in a slightly good way.
Not super great.
The last rule that we’re going to add here is,
whoops, what happened there?
I’m supposed to do that, yeah.
The last rule we’re going to add is
we must have ordering to our nodes, to the numbers in our nodes. So what do I mean by ordering? Well,
the whole reason that we want a binary search tree, at least usually, is because it’s really,
really fast to search through. This is going to be a tree that we can search through in log time,
which we’ll talk more about in another video. We’ll do time complexities and searching and stuff. But
in order for this to be a super fast tree to search through, we need to be able to
very quickly make a decision. Do we go down and to the left? Do we go down and to the right?
left do we go down into the right and every decision we make should help us eliminate half
of the remaining data set half of the tree at a time every time we go down a level and that’s only
possible if the nodes themselves are ordered so what i’m going to do is say every node that’s on
the left side or let’s say every descendant that’s on the left side of a node should be of a lesser
value than that particular node every node that is on the right side of a node meaning it’s a right
descendant of that node or part of the right subtree of the node should be greater than that
node. Please note that this would not allow us to support duplicate values in our tree.
You could use something like less than or equal to versus greater than if you wanted to support
duplicate values in your tree. You could also change the T type, you know, the template type
to a node from the data you want it to store to a list. So every single node has a list inside of it
and the items in the list are just, you know, the regular values that you wanted. There’s a whole
values that you wanted there’s a whole bunch of different ways you could actually do that
but for now we’re going to see our trees don’t support duplicate values
so okay we don’t support duplicate values but we need you know from left to right
the order needs to look sane and this is kind of why we’re drawing the tree in this special way
we’re trying to make our tree really easy to debug visually so check this out the way we’ve
drawn this every single node has its own x coordinate basically notice how the 12 there’s
nothing underneath it at least not directly underneath it the 33 the 34 all the nodes you
know you can draw a straight line down from the node and it shouldn’t cross over with any other
nodes or edges so that means now that we’ve drawn it this way and we’ve made sure that all the left
descendants are on the left and all the right descendants are on the right we could actually
just scan our eyes from left to right and be sure that we are seeing an increasing order or
Since duplicates aren’t allowed in this tree, we’ll say an increasing order or an ascending order.
So if we start at 45 and then we go to the right, we should see a higher number.
So if we look at 8, 8 is a lower number.
So this violates the ordering rule.
This is not a valid binary search tree.
It’s only a valid binary tree.
So sad.
Okay, so I could, you know, swap the 45 and the 8 or I could just increase the value of the 8 itself.
of the 8 itself, I think it’ll be faster for me to just increase the 8 value. So I’m going to make
it 52 now. So we’ve got 45, 52. Then we go to the right a little bit more. It should also increase.
So 52 should increase. I’m just going to randomly increase it to, you know, 59, let’s say. Then as
we go to the right, we see another number here. It is 76. That already is increased from 59.
So we don’t need, we don’t need to alter that number. Then we go to the right one more time
that because it’s lower than 76 so I’m going to put 87 then when we go to the right one more time
that’s the 34 down here that’s definitely a decrease so we have to increase it now so I’m
going to say 99 how about if I just do 92 yeah so now we have a 92 down here and then if we go
to the right a little bit more there’s the 99 and now we actually have a binary search tree let’s
just double check all the rules first off is this a graph yeah there’s nodes and edges there’s nothing
There’s nodes and edges.
There’s nothing weird happening.
There’s not like a edge floating in the middle of nowhere.
Is this a connected graph?
Yeah, it is.
Because every single node, if you followed, you know, the edges, you know, could find
every single other node.
Like the 45, it could find, you know, the 92 node if it just followed all these edges.
Notice again that these edges have no direction.
There’s no arrows on them.
So we could go up or down in any direction we want.
So that means the 76 can find everything else.
else and so this is a connected graph for sure okay now that we have a
connected graph is this an acyclic graph I don’t know about you but I can’t find
any cycles in the graph right like the 92 it goes out but it doesn’t come back in
same thing for the 76 if we went from the 76 up to the 87 and then took a
right turn we wouldn’t be able to come back towards it without repeating that
same edge so this is definitely an acyclic graph all of the nodes follow
they’re not involved in cycles is this a rooted tree yeah there’s only one common ancestor to the
entire tree it’s the 59 it’s the highest node in the entire tree and it’s common to all other of
all of its descendants um so let’s see i’m going to duplicate this real fast the next thing is
we arranged it hierarchically and we added the terminology of like i think i kind of just like
tried to sneak this one past you but we added the terminology of a left child and a right child
and a right child.
Right? We also added the terminology of a right subtree and a left subtree.
Just to clarify what I mean, what do I mean by a right subtree and a left subtree.
So imagine we’re considering the 59.
If we consider the 59, then the 52 is the root node of the left subtree of the 59 node.
If we consider the 59, then the 87 is the root node of the right subtree of the 59 node.
so the right child is basically the root of the subtree uh in in you know the right child is the
root of a subtree of the right subtree uh i think i’m getting muddled my words here okay
anyway so we have a little bit of terminology uh the 59 is the root node that’s like the
the only node in the entire tree without uh an ancestor or a parent so okay uh then we have a
Note, and the entire tree doesn’t have more than two children.
Notice how the 59 has two children.
That’s fine.
If it was three, that’s way too much.
52 has one.
87 has one.
No, 87 has two children.
99 has one child.
92 has zero children.
So, okay, we’re not violating that rule.
So, we definitely have a binary tree.
And then we, you know, kind of read from left to right.
Let me write down the numbers this time for fun.
physically without kind of like following edges or anything we just scan
our eyes from left to right we can see that we have an ascending list if we
supported duplicates it would be okay to just see a non decreasing list but we
see an increasing list or an ascended list ascending list okay whoops this is
left to right so this is actually a binary search tree and um i don’t know about you but i think i
need to like you know get a snickers or something right now because uh this video has been going on
for longer than i wanted it to go on so we’ve defined a binary search tree in future videos
we’ll talk about how to add nodes into a binary search tree how to build the tree what’s the time
complexity of the tree in various operations deleting nodes from a tree terminology like
terminology like what are these nodes called things like that so anyway thank you so much
for for watching i hope you learned a little bit of stuff and had a little bit of fun
i’ll see you at a later date in time
just kidding
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 uh if you could do me a please
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?
It’s a 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 do do me a kindness and uh and subscribe
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, 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, Hey, what’s up?
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 would really, it
it would really mean the world to me.
I would really appreciate it.
So again, thank you so much for watching this video
and enjoy the cool music
as I fade into the darkness,
which is coming for us all.
Thank you.
