Quick but thorough run-through of binary search tree terminology: root, leaves, internal nodes, subtrees, depth, height, ancestors, descendants, siblings, left/right child – everything clearly labeled on a working example.
Great for beginners, interview prep, or reviewing foundational BST concepts before coding insert/search/delete.
00:00 Introduction to BST Terminology
00:28 Root Node
01:10 Ancestors and Descendants
01:58 Children, Grandchildren, and Siblings
04:07 Internal Nodes vs External Nodes (Leaves)
05:34 Understanding Subtrees
06:09 Left Subtree and Right Subtree Examples
08:34 Depth of a Node
11:02 Height of the Tree
12:48 Height of Subtrees
17:32 Node Structure and Pointers Overview
18:12 Closing Remarks and Call to Action
=-=-=-=-=-=-=-=-=
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 talk about binary search tree terminology. If you saw my
previous video we talked about how to define a binary search tree meaning a
whole bunch of rules so that if the thing you’re looking at follows all the
rules then you know you’re actually looking at a binary search tree if not
then not. So see my previous video if you want to know for sure whether you’re
looking at a binary search tree. For now we’re just going to talk about some
Okay, so the first thing we should probably obviously talk about is the root node over here.
So I mean, well, in my previous video, we talked about nodes, right?
So this is kind of a graph with a whole bunch of rules on top of it.
That means we have nodes and edges.
So if you look at the very top node here, sometimes also referred to as a vertex,
I think in binary search tree terminology, we usually say nodes.
We usually say nodes. I can’t actually remember. But so look at the 42 there
That node is the root node of all other nodes. It’s the highest common ancestor in the entire tree. So this is the root node
First bit of terminology. Also, I tried to sneak past you ancestor
So these trees are supposed to be written in a way that kind of looks like they have a family hierarchy with one parent per
like not two children per parent, but just like one parent and then either zero or one or two
children. So we’ll say that ancestors are higher on the tree. So that means 42 is actually an
ancestor of 33. And it’s also an ancestor of 12. It’s also an ancestor of 19. Just anything that’s
higher is an ancestor of anything that’s lower. We could also say that 33 is an ancestor of 39
and 19 and so forth. You can probably also imagine that we have children and grandchildren. Yeah,
we do go that far in binary search trees. So the 42 node, it has two children. It has a left child
and a right child. The 33 is the left child. I’ll put LC for left child. And the 67 is its right
child. I’ll put an RC there. The 67 in turn has two children. The 56 has no children of its own.
the 33 has two children the 12 only has one child it was you know playing it safe i guess
you never know if these children are going to come out and just like run amok
and and engage in constant shenanigans so the 12 has a right child but no left child that’s okay
um in terms of going higher on the tree anything that is higher is an ancestor sorry i should have
said lower anything that’s higher is an ancestor anything that’s lower is a descendant so if we’re
If we’re looking at the 33 node, the 33 is a descendant of 42 because it’s the left child of 42.
It’s also an ancestor of anything that comes below it.
So it’s an ancestor of 12 and 39 and 19, right?
So if we’re looking at 33, we’ve got a left child over here and we’ve got a right child over here.
And then we have a grandchild, which is the 19 node.
We don’t really have left and right grandchildren.
You could say a grandchild in the left subtree or the right subtree.
subtree talk about sub trees in a second the 33 has a parent node which is just the 42 node
which is also the root node of course it’s got a sibling the 67 is the sibling you can tell
something’s a sibling because it’s got the same parent as you it’s the people that you’re usually
fighting with right anyway so if we’re looking at any node in particular it might have a whole bunch
of ancestors above the tree it might have a whole bunch of descendants below the tree
It has siblings or it usually has zero or one sibling because in a binary search tree,
we can only have up to two children per node.
It’s got sometimes, you know, grandparents and great grandparents and children and great
grandchildren.
So just think about the hierarchy like a family tree would have.
Okay, moving on to some more terminology.
Next thing is we have internal nodes and also external nodes.
So what do I mean by internal? Internal means a node has more than zero children. It has one or two children.
So I’m going to put internal on the 33 because the 33 node has children.
The 12 also has children, so it’s internal. The 39 does not have children, so it’s not internal.
67 has children, so it’s internal. And the root node, 42, also has children, so it’s considered internal.
That 42 has a lot of different names.
It’s the root node, it’s the greatest common ancestor,
it’s an internal node and so forth.
Notice how the other nodes that I have not highlighted,
they have zero children.
So when a node has zero children,
it’s known as an external node.
It’s also known as a leaf
because we’re talking about trees
and I guess it’s kind of like a nice synonym.
So the 19, the node with no children of its own is a leaf.
So is the 39.
So is the 56.
So is the 76.
I just want to point out also, if you were with me on my last video,
then the numbers need to be ordered from left to right.
But don’t worry, we’re going to do another video where we build a complete tree from scratch.
There’s some more terminology we should talk about.
So I’m going to get rid of all these externals and internals real fast.
Or the labels.
We should talk about the left subtree versus the right subtree.
left subtree versus the right subtree i mean what is a subtree anyway the subtree is basically
a subtree is basically just pick any node you want in the entire tree let’s pick
the 76 and then we’ll just pretend that it’s the root node of a separate tree starting with 76 so
if there was anything below it then all those nodes would be included so this 76 right here it
really has nothing underneath it it’s a leaf which means well it can be the root node of its own
the subtree is just going to be a tree of one node.
So kind of boring, right?
You’re boring.
If instead we decided to look at the 33,
which is a little bit more interesting,
and we called the 33 the root node of its own subtree,
then really what we’re saying is all these nodes here
are included in that subtree.
So if I told you, give me the subtree starting with node 33,
then you would say, oh, it’s 33, 12, 39, 19.
descendants of the subtree root node that we picked out. So subtree just means, you know,
like a little fragment or a portion of the original tree. You could also say that the
entire tree is a subtree of itself. If you chose the subtree root to be the real root node, I mean,
that’s not super useful, but you can do it. Anyway, so if we decide to say that the 67 is the root of
with 67 and below in terms of descendancy is going to be considered part of the subtree.
I’ve highlighted the left subtree and the right subtree of the root node because that’s usually
what we say. We’ll say this is the left subtree over here and then over here we’re going to say
this is the right subtree. Meaning if you look at any node at all, if it has a left child,
then that left child is the root node of the left subtree of the node in question. Same thing for
same thing for the right so if I say all right let me duplicate this real fast
let me get rid of actually this real fast too if I say okay give me the left subtree of the 33 node
well then you would know to include the 12 and the 19 because the left subtree of the 30 node
has to the 33 node has to start with the left child of the 33 node which would be the 12 and
And we’ll just say, okay, the 12 is now the root node of its own subtree.
And then anything that goes below it in descendancy is going to be considered part of that subtree.
So that highlighted subtree is the left subtree of the 33 node.
The 39 is the right subtree of the 33 node.
I think I just did the wrong color.
Let me do that in gray.
Right, so we can do left subtree and right subtree for any node in the entire tree.
if a node has no children, then there are no subtrees, but we can still look and check.
And if there are children, then we’ve got subtrees or left and right subtrees.
Okay, so now that we’re done talking about subtrees real fast, let’s talk about the depth of a node.
So for me, I like to say that the depth of the root node is zero.
And so I’ll just, I guess we could start off by putting a zero on the 42 indicating it has zero depth.
It has zero depth.
Imagine maybe it’s a buoy in the water and it’s just like sitting, floating like directly
on the water.
So it has no depth.
It’s just like kind of on the surface.
But if you draw your binary search trees in this nice pretty way where every single time
you go down a generation from parent to child, from parent to child, you maintain, I guess,
like the same Y coordinate for same leveled nodes, then it’s really easy to calculate
the depth of every single node.
of every single note let me show you what show you what i mean real fast you saw my video uh
previously then you already know this but the 42 it’s got two children so if i go down to get one
of its children i’m going down to the 33 and then i’m going down to the 67 right since those two
children are on the same i guess level as if we were looking at a family tree they should be
physically on the same level they should be on the same y coordinate or the same horizontal plane
plane if we go down one more level which means any child of 33 or any child of 67 then those all
should be lined up also so notice how these are all lined up on the same y coordinate then if we
go down another level then this 19 here is just kind of by itself because the tree is not very big
so if we draw the tree like this which is a really smart way because uh it’s easier to debug
whether it’s a valid binary search tree and all sorts of other things,
then we can easily write down the depth kind of on the side of the graph.
We can say, all right, here’s depth zero, and here’s depth one,
and here’s depth two, and here’s depth three.
Just every time you go down one level, you just increase the depth.
And now you know the depths of all the nodes in the entire tree pretty quickly.
The 19, I’m just going to maybe do this in red.
the 56 and the 76 have a depth of 2, the 33 has a depth of 1, and the 42 has a depth of 0.
So all these trees, sorry, all these nodes in the tree have their own depth,
which are very easy to calculate if you draw the tree well. The next thing after depth is the height
of the tree. So what is the height of the tree? Well, that’s basically the depth of the deepest
to the very deepest node what is the minimum number of nodes that you must touch when you
start at the root node and then find your way to the deepest possible node in the entire tree so
um if you if you notice the 19 node is definitely the deepest node in the entire tree
it’s got a depth of three which means the height of the entire tree is four heights
equals four and maybe i’ll change that to like just black or something okay
So, let’s do it the other way real fast.
If we’re kind of just walking down the tree, let’s start at the 42 and then we go down
to the 33, we’ve touched two nodes so far.
We go down to the 12, we’ve touched three nodes.
We go down to the 19, we’ve touched four nodes.
So the height of the tree is four or the number of nodes that you need to touch as you make
your way down towards the deepest node or just a shortcut is the deepest nodes depth
plus one.
And that’s the height of the tree.
you can also have a height of a left subtree and a height of a right subtree so let me just
what’s going on here i think my thing is crashing hello oh i was definitely crashing i think my cpu
is burning right now all right i’m going to be complaining about my new cpu for a long time
i sprung only a few bucks for the best cpu that this motherboard could hold but it’s an old
something percent um i’m eventually going to have to like build a brand new computer
anyway so uh suppose we’re looking at the 67 node and the question is you know what is the height
of the left subtree of the 67 node versus the right subtree of the 67 node well if you recall
the left subtree is just all the nodes that are included uh beginning with the root node of the
subtree of the 67 node well that’s just the 56 node totally by itself what’s the right subtree
of the 67 it’s just that 76 node all by itself what’s the depth of 56 and 76 they’re both depth
zero if we’re talking about relative depths per their subtrees that means what is the height of
the left subtree and the right subtree they’re just one because the depth is zero the maximum
depth is zero and if we want to get to the deepest node in one of those subtrees we’re just
end up touching the one node that’s in the in the subtree at all so that means uh
uh i don’t want to write down uh left subtree height right now so left subtree height of 67
is one right subtree height of 67 is also one so we can do this with any node we want you know what
is the uh what is the situation with the 33 node let’s do uh the 33 node yeah uh it has a left
It has a left subtree height of 2 and you can tell because, well, the left subtree starts with the left child and the left child is going to be the root node of its own subtree.
Notice how the maximum depth we can find here is 1, right?
Like if we start at depth 0 for the 12, considering like it’s a relative depth, that means we take the deepest node, which is the 19 node, which has a depth of 1.
We add 1 to that.
So that means the height of that subtree is 2.
if you wanted to find the deepest node in that whole subtree, how many nodes would you have to
touch to get there? We’d have to touch the 12 and then touch the 19. We touch two nodes, so the height
of that subtree is two. Maybe I’ll just put H equals two here. So now for the right subtree of
the 33 node, it’s kind of easier. We just basically only have one node to really look at.
that means that 39 has a depth of 0 and the right subtree has a height of 1.
Whoops, 8 equals 1.
I didn’t put two equal signs. I like to do two.
I like to do the comparison operator.
We could also do the same thing with the 42 node, right?
We can say, let’s get rid of all this stuff real fast.
We can do the 42.
Its left subtree starts with that 33 node.
33 node so I’m just going to highlight that real fast the 42 nodes left subtree has a height of
one two three and you can tell because the 33 has a depth of zero a relative depth of zero and
the 12 and the 39 have one and the 19 has two so the deepest node has a depth of two
so that means the height of that subtree is is three so I’m just going to like do this real fast
and then the right subtree of the 42 node, the root node of the entire tree, is going to be this.
So the root node has a depth of zero, depth of zero, and then these other leaves over here have
depth of ones, which means the height of this subtree is going to be two, or the deepest node
plus one, or the number of nodes you need to touch to find the deepest node. And 56 and 76,
those are both equally the deepest node in those trees okay so we talked about a bunch of
terminology here let me just double check my notes in case I forgot to to tell you anything
I think I’m all right well maybe okay maybe I should real fast just briefly mention that these
nodes I mean this is not really part of the video exactly but let’s let me just mention that these
whoops that’s dumb let me do a blue circle they would have you know there’s
like some sort of an object you would call it a node and then they would have
pointers they would have each of these nodes would have a pointer to its
parents and it would have a left child pointer that goes down into the left and
a right child pointer that goes down to the right and also a little slot in that
object for the data so I’m just going to put t type data and C++ I usually say
I usually say that the templated data type for a node or data structure is just the T type.
That just means you could put anything you want.
You could have your nodes hold integers, letters, strings, custom objects, whatever you want to do.
And we’ll talk about this more in future videos.
But long story short, I want you to just imagine that every node actually has three pointers inside of it pointing to something else, to other nodes,
graph because in a graph you could have like a whole bunch of different connections and that’s
usually managed by the actual graph object itself so anyway we’re done with terminology i hope you
learned a little bit of stuff and had a little bit of fun thanks for watching this video
tell your friends eat a donut and a chocolate and then be really happy and stuff okay i gotta go
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 to keep making videos in general so please do do me a
kindness and 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 control 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
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 uh
if you have a suggestion for uh clarifications or errata or just future videos that you want to see
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
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
Thank you.
