BST Terminology: Root, Leaves, Subtrees, Depth, Height, Ancestors & More

Neural Lantern

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   binary search tree, BST terminology, binary search tree explained, BST root node, BST leaf nodes, BST internal nodes, BST subtrees, left subtree, right subtree, tree depth, tree height, BST ancestors, BST descendants, binary tree terminology, data structures tutorial, BST for beginners, coding interview prep, computer science trees, binary search tree basics   =-=-=-=-=-=-=-=-=   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

Transcript

00:00Hello there! Let's talk about binary search tree terminology. If you saw my

00:05previous video we talked about how to define a binary search tree meaning a

00:10whole bunch of rules so that if the thing you're looking at follows all the

00:13rules then you know you're actually looking at a binary search tree. If not

00:17then not. So see my previous video if you want to know for sure whether you're

00:21looking at a binary search tree. For now we're just going to talk about some

00:25associated terminology. Okay so the first thing we should probably obviously talk

00:38about is the root node over here. So I mean well in my previous video we talked

00:42about nodes right? So this is kind of a graph with a whole bunch of rules on top

00:46of it. That means we have nodes and edges so if you look at the very top node

00:50here sometimes also referred to as a vertex I think in binary search tree

00:55terminology. We usually say nodes. I can't actually remember. But so look at

00:59the 42 there. That node is the root node of all other nodes. It's the highest common

01:05ancestor in the entire tree. So this is the root node. First bit of terminology.

01:11Also I tried to sneak past you ancestor. So these trees are supposed to be

01:17written in a way that kind of looks like they have a family hierarchy with one

01:21parent per child. Like not two children per parent but just like one parent and

01:27then either zero or one or two children. So we'll say that ancestors are higher on

01:34the tree. So that means 42 is actually an ancestor of 33 and it's also an

01:40ancestor of 12. It's also an ancestor of 19. Just anything that's higher is an

01:44ancestor of anything that's lower. We could also say that 33 is an ancestor of

01:5039 and 12 and 19 and so forth. You can probably also imagine that we have

01:56children and grandchildren. Yeah we do go that far in binary search trees. So the 42

02:01node it has two children. It has a left child and a right child. The 33 is the left

02:07child. I'll put LC for left child and the 67 is its right child. I'll put RC there. The 67

02:14in turn has two children. The 56 has no children of its own. So sad. The 33 has

02:20two children. The 12 only has one child. It was you know playing it safe I guess.

02:24You never know if these children are going to come out and just like run amok

02:28and engage in constant shenanigans. So the 12 has a right child but no left child.

02:33That's okay. In terms of going higher on the tree anything that is higher is an

02:41ancestor. Sorry I should have said lower. Anything that's higher is an ancestor.

02:45Anything that's lower is a descendant. So if we're looking at the 33 node the 33 is

02:51a descendant of 42 because it's the left child of 42. It's also an ancestor of

02:56anything that comes below it. So it's an ancestor of 12 and 39 and 19 right. So 30 if

03:02we're looking at 33 we've got a left child over here and we've got a right child

03:06over here and then we have a grandchild which is the 19 node. We don't really

03:11have left and right grandchildren. You could say a grandchild in the left

03:15subtree or the right subtree. Talk about subtrees in a second. The 33 has a parent

03:21node which is just the 42 node which is also the root node of course. It's got a

03:26sibling. The 67 is the sibling. You can tell something's a sibling because it's

03:31got the same parent as you. It's the people that you're usually fighting with right.

03:35Anyway so if we're looking at any node in particular it might have a whole bunch

03:39of ancestors above the tree. It might have a whole bunch of descendants below the

03:43tree. It has siblings or it usually has zero or one sibling because in a binary

03:50search tree we can only have up to two children per node. It's got sometimes you

03:55know grandparents and great-grandparents and children and great-grandchildren. So

04:00just just think about the hierarchy like a family tree would have. Okay moving on to

04:05some more terminology. Next thing is we have internal nodes and also external nodes.

04:12So what do I mean by internal? Internal means a node has more than zero children. It

04:17has one or two children. So I'm gonna put internal on the 33 because the 33 node has

04:24children. The 12 also has children so it's internal. The 39 does not have children so

04:31it's not internal. 67 has children so it's internal. And the root node 42 also has

04:38children so it's considered internal. That 42 has a lot of different names. It's the

04:42root node, it's the greatest common ancestor, it's an internal node and so forth. Notice

04:47how the other nodes that I have not highlighted they have zero children. So when a node has

04:52zero children it's known as an external node. It's also known as a leaf because

04:59we're talking about trees and I guess it's kind of like a nice synonym. So the

05:0319, the node with no children of its own, is a leaf. So is the 39, so is the 56,

05:11so is the 76.

05:14I just want to point out also if you were with me on my last video then the numbers

05:18need to be ordered from left to right but don't worry we're gonna do another video

05:21where we build a complete tree from scratch. There's some more terminology we should talk

05:26about so I'm gonna get rid of all these externals and internals real fast or the labels. We

05:35should talk about the left subtree versus the right subtree. I mean what is a subtree anyway?

05:39The subtree is basically a subtree is basically just pick any node you want in the entire tree. Let's

05:44pick the 76 and then we'll just pretend that it's the root node of a separate tree starting with 76.

05:52So if there was anything below it then all those nodes would be included. So this 76 right here it

05:58really has nothing underneath it. It's a leaf which means well it can be the root node of its own

06:03subtree but the subtree is just going to be a tree of one node. So kind of boring right? You're

06:08boring.

06:09If instead we decided to look at the 33 which is a little bit more interesting and we called the

06:1433

06:14the root node of its own subtree then really what we're saying is all these nodes here are included

06:20in that subtree. So if I told you give me the subtree starting with node 33 then you would say

06:26oh it's

06:2633, 12, 39, 19. All of the nodes that are descendants of the subtree root node that we picked out.

06:36So subtree just means you know like a little fragment or a portion of the original tree.

06:40You could also say that the entire tree is a subtree of itself if you chose the subtree root to

06:46be

06:47the real root node. I mean that's not super useful but you can do it.

06:52Anyway so if we decide to say that the 67 is the root of its own subtree then

06:57well same thing right? Any node starting with 67 and below in terms of descendancy is going to be

07:03considered part of the subtree. I've highlighted the left subtree and the right subtree of the root

07:09node because that's usually what we say. We'll say this is the left subtree over here and then over

07:16here we're going to say this is the right subtree. Meaning if you look at any node at all if

07:22it has a

07:22left child then that left child is the root node of the left subtree of the node in question. Same

07:29thing

07:29for the right. So if I say all right let me duplicate this real fast. Let me get rid of

07:36actually this real

07:36fast too. If I say okay give me the left subtree of the 33 node well then you would know

07:44to include

07:45the 12 and the 19 because the left subtree of the 30 node has to the 33 node has to

07:51start with the left

07:52child of the 33 node which would be the 12 and we'll just say okay the 12 is now the

07:58root node

07:59of its own subtree and then anything that goes below it in descendancy is going to be considered part of

08:03that subtree. So that highlighted subtree is the left subtree of the 33 node. The 39 is the right subtree

08:14of the 33 node. I think I just did the wrong color let me do that in gray. Right so

08:20we can do left subtree and

08:21right subtree for any node in the entire tree. I mean if they if they if a node has no

08:25children

08:26then there are no subtrees but we can still look and check and if there are children then we've got

08:31subtrees or left and right subtrees. Okay so now that we're done talking about sub trees real fast

08:38let's talk about the depth of a node. So for me I like to say that the depth of the

08:43root node is zero

08:44and so I'll just uh I guess we could start off by putting a zero on the 42 indicating it

08:52has zero

08:52depth imagine maybe it's a buoy in the water and it's just like sitting floating like directly

08:57on the water so it has no depth it's just like kind of on the surface.

09:02But if you draw your binary search trees in this nice pretty way where every single time you go down

09:08a generation from parent to child from parent to child you maintain I guess like the same y coordinate

09:14for same leveled nodes then it's really easy to calculate the depth of every single node. Let me

09:21show you what show you what I mean real fast. You saw my video uh previously then you already know

09:25this

09:25but the 42 it's got two children so if I go down to get one of its children I'm going

09:32down to the 33 and

09:33I'm going down to the 67 right since those two children are on the same I guess level as if

09:40we

09:40were looking at a family tree they should be physically on the same level they should be on

09:44the same y coordinate or the same horizontal plane. If we go down one more level which means any child

09:52of 33 or any child of 67 then those all should be lined up also so notice how these are

09:59all lined up

10:00on the same y coordinate. Then if we go down another level uh then this 19 here is just kind

10:05of by

10:05itself because the tree is not very big. So if we draw the tree like this which is a really

10:11smart way

10:11because uh it's easier to debug uh like your whether whether it's a valid binary search tree and all

10:18sorts of other things then we can easily uh write down the depth kind of on the side of the

10:24graph we can

10:24say all right here's depth zero and here's depth one and here's depth two and here's depth three

10:29just every time you go down one level you just increase the depth and now you know the depths of

10:34all the nodes in the entire tree pretty quickly uh the 19 I'm just going to maybe do this in

10:39red

10:40the 19's got a three the 12 the 39 the 56 and the 76 have a depth of two the

10:4733 has a depth of one

10:49and the 42 has a depth of zero so all these trees sorry all these nodes in the tree have

10:55their own

10:55depth which are very easy to calculate if you draw the tree well. The next thing after depth is the

11:02height of the tree so what is the height of the tree? Well that's basically the depth of the deepest

11:08node plus one or if you try to find a path to the very deepest node what is the minimum

11:14number of

11:15nodes that you must touch when you start at the root node and then find your way to the deepest

11:19possible node in the entire tree so um if you if you notice the 19 node is definitely the deepest

11:26node

11:26in the entire tree it's got a depth of three which means the height of the entire tree is four

11:32heights

11:35equals four and maybe i'll change that to like just black or something okay

11:41so uh let's do it uh the other way real fast uh if we're kind of just walking down the

11:46tree let's

11:46start at the 42 and then we go down to the 33 we've touched two nodes so far we go

11:51down to the 12 we

11:53touch three nodes we go down to the 19 we've touched four nodes so the height of the tree is

11:58four or the

11:58number of nodes that you need to touch as you make your way down towards the deepest node or just

12:02a

12:03shortcut is the deepest nodes depth plus one and that's the height of the tree you can also have

12:10a height of a left subtree and a height of a right subtree so let me just what's going on

12:14here i think

12:15my thing is crashing hello oh i was definitely crashing i think my cpu is burning right now all right

12:24i'm going to be complaining about my new cpu for a long time

12:28i sprung only a few bucks for the best cpu that this motherboard can hold but it's an old motherboard

12:34so my upgrade was about 30 something percent um i'm eventually going to have to like build a brand

12:39new computer anyway so uh suppose we're looking at the 67 node and the question is you know what is

12:48the height of the left subtree of the 67 node versus the right subtree of the 67 node well if

12:55you recall

12:55the left subtree is just all the nodes that are included uh beginning with the root node of the

13:02subtree so if we say the left subtree of the 67 node well that's just the 56 node totally by

13:08itself

13:08what's the right subtree of the 67 it's just that 76 node all by itself what's the depth of 56

13:15and 76

13:16they're both depth zero if we're talking about relative depths uh for their subtrees that means what is

13:22the height of the left subtree and the right subtree they're just one because the depth is zero the

13:27maximum depth is zero and if we want to get to the deepest node in one of those subtrees we're

13:31just

13:32going to end up touching the one node that's in the in the subtree at all so that means uh

13:38uh i don't want to write down uh left subtree height right now so left subtree height of 67 is

13:44one

13:45left right subtree height of 67 is also one so we can do this with any node we want you

13:51know what is

13:51the uh what is the situation with the 33 node let's do uh the 33 node yeah uh it has

14:00a left subtree height

14:01of two and you can tell because well the left subtree starts with the left child and the left child

14:07is

14:07going to be the root node of its own subtree notice how the maximum depth we can find here is

14:13uh is one

14:15right like if we start at uh depth zero for the 12 considering like it's a relative depth uh that

14:21means we take the deepest node which is the 19 node which has a depth of one we add one

14:25to that so that

14:25means the height of that subtree is two or if you wanted to find the deepest node in that whole

14:30subtree

14:30how many nodes would you have to touch to get there we'd have to touch the 12 and then touch

14:34the 19 we

14:36touch two nodes so the height of that subtree is two maybe i'll just put h equals two here

14:44um uh so now for the right subtree of the 33 node it's kind of easier uh we just basically

14:50only have

14:51you know one node to really look at so the right subtree is just that 39 node that means that

14:5739 has

14:57a depth of zero and the right subtree has a height of one whoops eight equals one i didn't put

15:06two

15:06equal signs i'd like to do two i like to do the comparison operator um we could also do the

15:12same

15:13thing with the 42 node right we can say let's get rid of all this stuff real fast

15:18we can do uh the 42 its left subtree uh starts with that 33 node so i'm just going to

15:25highlight

15:26that real fast uh the 42 nodes left subtree has a height of one two three and you can tell

15:32because

15:34um the 33 has a depth of zero a relative depth of zero and um the 12 and the 39

15:40have one and the 19

15:41has two so the deepest node has a depth of two so that means the height of that subtree is

15:46uh is three

15:48so i'm just going to like do this real fast height is three and then the right subtree of the

15:5342 node the

15:54root node of the entire tree is uh going to be this so the root node has a depth of

16:01zero

16:03depth of zero and then these other leaves over here have depths of ones which means the height

16:10of this subtree is going to be two or the deepest node plus one or the number of nodes you

16:16need to

16:16touch to find the deepest node and 56 and 76 those are both equally the deepest node in those trees

16:23okay so we talked about uh a bunch of terminology here let me just double check my notes

16:29in case i forgot to to tell you anything i think i'm all right well maybe okay maybe i should

16:34real fast

16:36just briefly mention uh that these nodes i mean this is not really part of the video exactly but let's

16:41let me just mention that these nodes are objects right in your code um so they would have whoops that's

16:49dumb let me do a blue circle they would have you know there's like some sort of an object you

16:55would call it a node and then they would have pointers

16:59they would have each of these nodes would have a pointer uh to its parents and it would have a

17:03left child pointer that goes down into the left and a right child pointer that goes down to the

17:07right and also a little slot in that object for the data so i'm just going to put t-type

17:14data

17:14in c++ i usually say um that the templated data type for a node or data structure is just the

17:23t-type

17:23that just means you could put anything you want like you could have your nodes hold integers letters

17:28strings custom objects whatever you want to do um and we'll talk about this more in future videos

17:34but long story short uh i want you to just imagine that every node actually has three pointers inside

17:39of it pointing to something else to other nodes rather than thinking of it like a graph because

17:45in a graph you could have like a whole bunch of different connections and that's usually managed by the

17:50actual graph object itself so anyway we're done with terminology i hope you learned a little bit

17:56of stuff and had a little bit of fun thanks for watching this video tell your friends eat a donut

18:02and then chocolate and then be really happy and stuff okay i gotta go i'm going too far see you

18:09at a

18:09later date and time hey everybody thanks for watching this video again from the bottom of my heart i really

18:17appreciate it i do hope you did learn something and have some fun uh if you could do me a

18:22please a small

18:23little favor could you please subscribe and follow this channel or these videos or whatever it is you do on

18:29the current social media website that you're looking at right now um it would really mean the world to

18:33me and it'll help make more videos and grow this community so we'll be able to do more videos longer

18:39videos better videos or just i'll be able to keep making videos in general so please do do me a

18:45kindness

18:46and uh and subscribe you know sometimes i'm sleeping in the middle of the night and i just wake up

18:50because

18:50i know somebody subscribed or followed it just wakes me up and i get filled with joy that's exactly what

18:55happens every single time so you could do it as a nice favor to me or you could you could

18:59troll me

19:00if you want to just wake me up in the middle of the night just subscribe and then i'll i'll

19:03just wake

19:03up i promise that's what will happen also uh if you look at the middle of the screen right now

19:09you

19:09should see a qr code which you can scan in order to go to the website which i think is

19:13also named somewhere

19:14at the bottom of this video and it'll take you to my main website where you can just kind of

19:18like see

19:19all the videos i published and the services and tutorials and things that i offer and all that good stuff

19:24and uh if you have a suggestion for uh uh clarifications or errata or just future videos

19:33that you want to see please leave a comment or if you just want to say hey what's up what's

19:37going on

19:38you know just send me a comment whatever i also wake up for those in the middle of the night

19:41i get

19:42i wake up in a cold sweat and i'm like it would really it really mean the world to me

19:47i would really

19:47appreciate it so again thank you so much for watching this video and um enjoy the cool music

19:54i wake as as i fade into the darkness which is coming for us all

20:02so

20:10so

20:12so

Category

Transcript

Comments

Recommended