Binary Search Tree Definition Explained Step by Step

Neural Lantern

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   binary search tree, bst, binary search tree definition, what is a binary search tree, bst rules, binary tree vs binary search tree, bst ordering property, left subtree right subtree, data structures, binary search tree explained, bst for beginners, computer science, algorithms, tree data structure, rooted binary tree, acyclic graph, connected graph   =-=-=-=-=-=-=-=-=   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:01hey there let's talk about binary search trees specifically in this video i want to help you

00:06define and identify what is a binary search tree all the rules that go into determining whether

00:12or not something is a binary search tree so you can you can tell that you're looking at one or

00:15whether you're not looking at one uh we'll talk about some terminology but uh keep in mind i'm

00:21going to save searching and and sorting and like you know deleting and adding items and a whole

00:27bunch of extra stuff especially the hard stuff for videos that'll come right after this one for

00:32now we're just going to talk about what is a binary search tree

00:42so you can see on the screen right here i hope uh that we have a binary search tree uh

00:46let's see can

00:46you see that yeah i think you probably can or yeah i think you can um this is not drawn

00:51quite as well

00:52as i would like to draw ours uh i'll tell you i'll tell you uh how to do that in

00:56a little while but

00:58when you draw a tree in a really really nice pretty aligned way it's way easier to debug

01:02it's way easier to tell that you're looking at something that is sorted um and so forth anyway

01:07okay so first let's start off with a graph so this is not a video about graphs uh i guess

01:16i can probably

01:16expect that you already kind of know what a graph is at this point in time but for now we'll

01:20just say

01:21that a graph is a collection of nodes and edges so what do i mean by nodes well just imagine

01:27there's like a little circle here that contains some sort of data if you know data structures

01:32already then uh there would be a t type sitting inside the node we'll just call the t type an

01:37integer and so for our uh nodes for our trees we're just going to say that they hold integers even

01:44though you know technically speaking in a binary search tree or a graph you could have all sorts of

01:48different data types is this working i think it's lagging okay so i'm just gonna you know grab uh

01:56this and sort of like duplicate it and just duplicate it again i'm just gonna make a bunch

01:59of duplicates something is definitely wonky about my setup right now i think uh i just upgraded the

02:06camera and the cpu is maxed out i just upgraded the cpu on this computer too oh well okay so

02:13uh

02:16we uh aren't going to support duplicate values in our binary search tree but for now i'm going to say

02:20it doesn't really matter for the graph uh later on we'll start making sure there's no duplicate data

02:26uh for now i think i can probably do that somewhat quickly let's see seven six okay so uh a

02:32graph you

02:33know for the for our purposes right now a graph is just basically a collection of nodes and edges it

02:37could be empty it could be just nodes it couldn't just be edges it would have an edge always has

02:42to

02:42have a node or two connected to it so we just have like a bunch of nodes inside of the

02:47nodes we have t

02:47type data values uh this is a valid graph but i'm going to draw some edges randomly here so we're

02:54going

02:54to do this um it doesn't really matter i'm just randomly drawing edges okay actually i should probably

03:02do maybe like one that's kind of separated okay so this is a graph uh this is not a binary

03:08search

03:08tree so let's add a bunch of rules let me just pull up my rules real fast here okay so

03:14what is

03:14a binary search tree um first we'll start off with the graph like we have here and then we'll say

03:20that

03:20the graph must be connected what is a connected graph a connected graph is basically a graph where

03:25every single node can find every single other node or find a find a path to every single other node

03:31only following along edges and only by respecting the direction of edges you can see this particular

03:36graph is undirected meaning the edges don't really have a direction to them so that means we could

03:41travel along in any direction from node to node so just as a real quick uh you know i guess

03:47like

03:47tutorial i'm going to say is 8 connected to every single other node uh well it can find a path

03:52to 12

03:53and it can find a path to 33 and it can find a path to 76 and 45 but it

03:58cannot find a path to 99 which means

04:00this is not a connected graph so that's the first rule that we have to implement here we're going to

04:04say this graph needs to be upgraded or modified so that it will be a connected graph so i'm going

04:11to

04:11basically just start randomly adding edges until this is a connected graph i'm going to do maybe like

04:17an edge from um 99 to 12 there and then now i think this is a connected graph but let's

04:23double check real

04:24fast so connected graph uh you know what uh i'm going to put graph connectedness in another video

04:33to keep this one short for now uh check out my other videos if you would like to see whether

04:39or not

04:39a graph is connected but long story short as i just said if every single node can find a path

04:43to

04:44every single other node without you know skipping where there is no edge uh then it's connected okay

04:49so that's the first thing the next thing that we need let me just put the words uh connected up

04:55here

04:56we need a connected graph the next thing that we need is uh we need an acyclic graph which basically

05:02means a graph with no cycles what is a cycle

05:07a cycle is can you find a path in this graph that starts at one node and ends at the

05:15same node

05:16without repeating any edges so for example if i was asking you know is 76 involved in any cycles well

05:22we could go from 76 to 33 and then 12 um and you know we could kind of take 8

05:2945 12 again

05:31but by the time we turn around and try to get back to the 33 we've already crossed this edge

05:35twice

05:36so that means the 76 is not involved in any cycles because we cannot find our way back to 76

05:43without repeating an edge so 76 is okay i'm just going to maybe put like a little checkbox here

05:51and uh you can also tell that the 33 is not involved in any cycles because we go down to

05:56the 76 and

05:57come back up to 33 we already repeated an edge so that's not valid same thing for going from the

06:0233

06:02to the 12 in the back again uh same thing for the 34 same thing for the 99 but if

06:09you look at the 12

06:10here we could actually find a cycle we could go from the 12 to the 8 and then from the

06:158 to the 45

06:16and from the 45 to the 12 now we're back where we started we're at the 12 note again and

06:22we did not

06:22repeat any edges so this is not a cyclic this is a cyclic graph it's got a cycle so that's

06:30the next

06:30rule we want to add we want to make sure that our graph has no cycles so uh the next

06:38rule i'm just

06:38going to say is is going to be satisfied by me removing some edges uh at random so i don't

06:44know

06:44let's get rid of uh the 8 to the 45 connection see if that works um let's see well wait

06:53a minute

06:53what did i just do something happened here i just accidentally oh i erased too many edges

06:57from the last slide okay let me add that one back in 33 to 76 that was supposed to be

07:01there

07:02so now we have an acyclic graph um and we can consider we can consider this graph a tree

07:09the next thing we need to do is uh add a hierarchy to this tree so this is going to

07:14make more sense

07:15in a little bit but for now i'm going to say uh we'll imagine a family tree kind of it's

07:20not

07:20really exactly a family tree but you know imagine there are parents and children and grandchildren

07:25and we'll just try to like we'll try to rank children according to uh you know when they were

07:32born or or how many parents or children they have you know their descendancy their lineage whatever you

07:37want to call it so i think i'm just gonna maybe move the eight up a little bit so that

07:42it's on the

07:42same rank uh with the 12 and the 33 so i'm just going to move these up a little bit

07:47and then redo

07:49uh their connecting lines so i'm going to do this and that and then we'll we'll say that the 76

07:57is still a child of the 33 so i'll just kind of move it over here or sorry we never

08:02said it was a

08:03child now we're saying it's a child because when you go from top to bottom imagine like a

08:07family tree we'll say we have parents and children the children or the descendants are lower

08:12the ancestors or the parents or the grandparents are higher maybe i want to put this 45 over on the

08:18left so that it's a child of the eight node and maybe i'll say that the uh the 99 node

08:25is a child

08:26of the 12 node okay so uh eventually this is going to look not exactly like a family tree because

08:33usually

08:33the family tree we have two parents that go to one or more children in this type of tree in

08:39eventually

08:39our binary tree we're going to have one parent uh that has you know children just by itself like

08:46asexual reproduction we're pretending to be bacteria again or whatever

08:53what was that what was that comedy skit a long time ago tiny elvis

08:57and he was like hey see that protozoa over there the thing is huge anyone no okay

09:05so the next rule we need is we must have a rooted tree what is a rooted tree actually let

09:11me let me

09:11let me clean up the the lineage real fast the heritage i want to make nodes that have the same

09:18like

09:19level with respect to their ancestors to have the same physical uh y coordinate the same physical level so

09:25notice how the 99 i just moved it down a little bit because i wanted it to look like it's

09:31the same

09:32you know number of generations lower uh than the top row so like with aid it had a child 45

09:37so that's

09:38one level down 33 had a child that's one level down that's a 76 and uh the 12 also one

09:44level down

09:45would have been 99 but the 99 was kind of too physically high this will help you debug your binary

09:50trees uh in the future anyway so i'm just going to clean this up right now and uh now that

09:56we have

09:56you know parent child relationships we need to look at the most common ancestor in the whole entire

10:02tree or if there is one so notice how uh i guess i'm just kind of using the word ancestor

10:07without explaining it

10:08so your ancestors are the people that you're disappointing when you don't study for the final exam or

10:14for your work interview or whatever it is um ancestors came before us right like my my my

10:21parents are my ancestors my grandparents are also my ancestors my great-grandparents are also my

10:26ancestors going down in the family tree are your descendants you know my my children are my descendants

10:32my grandchildren are my descendants my great-grandchildren are my descendants and so forth so

10:38if you look at the number 34 here what is the greatest ancestor that it has well if you just

10:43go

10:43up and up and up until you can't go up anymore it's the 12th so that means the greatest ancestor

10:49of

10:50at least in this tree of the 34 is the 12th uh the 45 the highest you can go is

10:56the 8. notice how 8 and

10:5812 and 33 are siblings there's not really like a parent-child relationship they're connected sideways

11:03we'll eventually get rid of the sideways connections for our binary search trees but for now

11:07we have some siblings and so we actually have three different greatest ancestors in this tree

11:12we've got 8 and 12 and 33 and that's no good so the next rule that we need is we

11:17need one common

11:19ancestor for every single uh other node in the entire tree um so i'm going to duplicate this slide

11:26right here and i'm going to say we need to clean this up so we got to choose 8 or

11:3012 or 33 i don't know

11:32i'm just going to maybe say that 8 and it's 45 are children of uh the 12 so i'm just

11:39going to redraw

11:40a line here arbitrarily so i'm gonna go like that notice how i'm trying to keep the 8 the 99

11:46and the 76

11:47on the same y coordinate the same level now we have two uh you know greatest ancestors we need to

11:54have

11:54only one so i think i'm probably going to say that the 33 and the 76 are going to become

12:00children of the

12:0012 node just for simplicity so i'm going to put this over here i'm going to get rid of that

12:06little line

12:07and i'm going to like move this over here this is a gross tree but we'll fix it soon

12:12we'll do that all right okay okay okay and then i have to get rid of that little sibling line

12:23and

12:23then i have to add another line to say that 33 is a child of 12 okay so now we

12:29have a rooted tree what

12:30we had before was an unrooted tree or just like not a rooted tree because there was no root there

12:35was

12:35no greatest common ancestor to the entire rest of the tree but now we can say that 12 is the

12:42root of the

12:42tree because it's the ancestor for all other nodes uh i guess even if 12 was by itself we could

12:47call

12:48it a rooted tree it just wouldn't be a very good example so i'm going to actually get rid of

12:52the

12:52word acyclic here since we already handled that and i'm going to do i'm going to say that 34 is

12:58greatest ancestor is 12 99 greatest ancestor is 12 33 greatest ancestor 76 all the nodes in the tree

13:05the greatest ancestor is 12 and it's common to all of them so now we have a rooted tree maybe

13:11i

13:11should type in my doomed i really hope the screen i really hope the screen uh cast doesn't freeze

13:22it probably will upgraded the cpu it's 33 faster uh than it was before but i didn't want to pay

13:31for

13:31a new motherboard so i am still using an old cpu even though it's new to me dang it i'm

13:38gonna have to

13:38spend like 500 okay uh so the next rule is so we have a rooted tree and now let's rearrange

13:46everything

13:46hierarchically which we already kind of did so uh there's not really much to do here except uh let's

13:53add let's see yeah let's well yeah let's erase this we did hierarchical organization

14:03we probably just need to move on to our next rule which is to say that if our rooted tree

14:08is to become

14:09a binary tree then each node in the entire tree cannot have more than two children every single

14:15node in the entire tree can have zero or one or two children if there are three or more anywhere

14:21in the

14:22entire tree then it's not a binary tree so okay that means uh you know the 45 is okay because

14:28it has no

14:29children all the rows all the all the the leaves at the bottom are okay all these nodes over here

14:35okay because they just have one child but the 12 node the root of the tree uh it's got three

14:40children

14:40and that violates the rule so now we need to rearrange this so i think i'm going to just move

14:45these numbers

14:46down here maybe um whoops maybe move these nodes uh just like a little bit lower uh so that we

14:54can have

14:54them become a descendants of the 33 node so i'm going to do this

15:03okay so cool now we have a binary tree and now we need to rearrange the drawing a little bit

15:08this is

15:08not part of the definition but this will make it easier to debug your trees so what i want to

15:14do is

15:14make it so that every left descendant of a node appears physically on that node's left side so like

15:21uh you know to the left in terms of the x coordinate uh every right descendant of a node should

15:27appear

15:27on its right side uh or like further to the right on the x coordinate so sort of similar to

15:33you know

15:33like the y coordinate ranking uh but notice how the 12 its left uh child is 8 and its right

15:39child is 33

15:40so that means all the nodes uh here on the left side you know that come underneath the 8 are

15:46left

15:46descendants or you could say that they are in the left subtree of the 12. so uh they're okay because

15:548 is to the left of 12 and 45 is to the left of 12. but notice how 33 is

15:59a right child of 12 and it's

16:02part of the right subtree it's part of the right descendancy but it's physically on the left of 12.

16:07that's going to be really bad because it'll be harder to debug our trees later so i'm just going to

16:11slide it over without rearranging the tree and i usually try to split the difference here so

16:17notice how i've got these two nodes here and then their parent is kind of like physically in the

16:22middle that will also help you debug in the future so i'm going to do this wrong let me get

16:29the blue

16:30i'm going to do this make sure that my ranking is still okay not the best most neatest tree and

16:35so

16:35now i'm going to look at the 8 its left subtree or its left uh descendancy uh all of those

16:41nodes

16:42which is just the 45 are physically to the left so that's okay now i'm going to look at the

16:4733

16:49its left child 76 uh is the only thing that's on the left side in the left subtree so that's

16:53all

16:53right uh probably the 33 i think it's still a little lopsided i probably could have you know dragged

16:59it a little bit more to the right but i'm going to leave it uh so the 33 and the

17:0376 are okay

17:04and then the 99 is a right descendant or it's part of the right subtree of the 33 so it

17:09should be on

17:09the right side it is that's good uh the 34 should be on the right side of the 33 because

17:15it's it's a

17:16it's part of the right subtree of 33 it's part of the right descendancy um and it should also be

17:22on

17:22the left side of the 99 because it's part of the left uh subtree of the 99 so so far

17:26this is okay it's not

17:27the best uh drawing so now we have a binary tree and uh we have kind of drawn it in

17:34a slightly good

17:34way not super great the last rule that we're going to add here is uh whoops what happened there

17:41supposed to do that yeah the last rule we're going to add is we must have ordering to our nodes

17:47uh to

17:47the numbers in our nodes so what do i mean by ordering well the whole reason that we want a

17:52binary

17:52search tree at least usually is because it's really really fast to search through this is going

17:57to be a tree that we can search through in log time which we'll talk more about in another video

18:01we'll do time complexities and searching and stuff but in order for this to be a super fast tree to

18:07search through we need to be able to to uh very quickly make a decision do we go down into

18:12the left

18:12do we go down into the right and every decision we make should help us eliminate half of the remaining

18:17data set half of the tree at a time every time we go down a level and that's only possible

18:23if the nodes themselves are ordered so what i'm going to do is say every node that's on the left

18:29side or let's say every descendant that's on the left side of a node should be of a lesser value

18:35than

18:35that particular node every node that is on the right side of a node meaning it's a right descendant

18:40of that node or part of the right subtree of the node should be greater than that node

18:45please note that this would not allow us to support duplicate values in our tree

18:49you could use something like less than or equal to versus greater than if you wanted to support

18:54duplicate values in your tree you could also change the t type you know the template type

18:58to a node from the data you wanted to store to a list so every single node has a list

19:04inside of it

19:05and the items in the list are just you know the regular values that you wanted there's a whole bunch

19:09of different ways you could actually do that but for now we're going to see our trees don't support

19:13duplicate values so okay we don't support duplicate values but we need you know from left to right

19:18the order needs to look sane and this is kind of why we're drawing the tree in this special way

19:23we're trying to make our tree really easy to debug visually so check this out the way we've

19:30drawn this every single node has its own x coordinate basically notice how the 12 there's

19:35like you know pretty much nothing underneath it at least not directly underneath it the 33 the 34

19:39all the nodes you know you can draw a straight line down from the node and it shouldn't cross

19:43over with any other nodes or edges so that means now that we've drawn it this way and we've made

19:49sure that all the left descendants are on the left and all the right descendants are on the right

19:54we could actually just scan our eyes from left to right and be sure that we are seeing an increasing

20:00order or usually we say non-decreasing order but um since duplicates aren't allowed in this tree we'll

20:08say an increasing order or an ascending order so if we start at 45 and then we go to the

20:14right we

20:14should see a higher number so if we look at 8 8 is a lower number so this violates the

20:19ordering rule

20:19this is not a valid binary search tree it's only a valid binary tree this is so sad okay so

20:27uh i could

20:28you know swap the 45 and the 8 or i could just increase the value of the 8 itself i

20:33think it'll be

20:34faster for me to just increase the 8 value so i'm going to make it 52 now so we got

20:3845 52 then we go

20:40to the right a little bit more it should also increase so 52 should increase i'm just going

20:44to randomly increase it to uh you know 59 let's say then as we go to the right we see

20:49another number

20:50here it is 76 that already is increased from 59 so we don't need we don't need to alter that

20:55number

20:55then we go to the right one more time and it's 33 we definitely need to increase that because it's

21:00lower than 76 so i'm going to put 87 then when we go to the right one more time that's

21:06the 34 down

21:07here that's definitely a decrease so we have to increase it now so i'm going to say 99 uh how

21:13about

21:13if i just do 92 yeah uh so now we have a 92 down here and then if we go

21:19uh to the right a little bit

21:20more there's the 99 and now we actually have a binary search tree let's just double check all the rules

21:26first off is this a graph yeah there's nodes and edges there's nothing weird happening there's

21:30not like a edge floating in the middle of nowhere uh is this a connected graph yeah it is because

21:36every single node if you followed you know the edges um you know could find every single other node

21:43like the 45 it could find you know the 92 node if it just followed all these edges uh notice

21:49again

21:49that these edges have no direction there's no arrows on them so we could go up or down in any

21:53direction

21:53we want so that means the 76 can find everything else and so this is a connected graph for sure

22:00okay now that we have a connected graph is this an acyclic graph i don't know about you but i

22:04can't

22:05find any cycles in the graph right like the 92 it goes out but it doesn't come back in uh

22:10same thing for

22:10the 76 if we went from the 76 up to the 87 and then took a right turn we wouldn't

22:16be able to come back

22:17towards it without repeating that same edge so this is definitely an acyclic graph all of the nodes

22:23follow that rule they're not involved in cycles is this a rooted tree yeah there's only one common

22:29ancestor to the entire tree it's the 59 it's the highest node in the entire tree and it's common

22:34to all other of all of its descendants um so let's see i want to duplicate this real fast the

22:42next thing

22:42is we arranged it hierarchically and we added the terminology of like i think i kind of just like

22:48tried to sneak this one past you but we added the terminology of a left child and a right child

22:55right we also added the terminology of a right subtree and a left subtree

22:59just to clarify what i mean what do i mean by a right subtree and a left subtree so imagine

23:03we're

23:04considering the 59 if we consider the 59 then the 52 is the root node of the left subtree of

23:11the 59 node

23:12if we consider the 59 then the 87 is the uh is the root node of the right subtree of

23:19the 59 node so the

23:20right child is basically the root of the subtree uh in in you know the right child is the root

23:27of a

23:27subtree of the right subtree uh i think i'm getting muddled my words here okay anyway so we have uh

23:33a

23:34little bit of terminology uh the 59 is the root node that's like the the only node in the entire

23:39tree

23:39without uh an ancestor or a parent so okay uh then we have a binary tree because every single node

23:48in

23:48the entire tree doesn't have more than two children notice how the 59 has two children that's fine

23:53if it was three that's way too much 52 has one 87 has uh one no 87 has two children

24:0099 has one child

24:0292 has zero children so okay we're not violating that rule so we definitely have a binary tree

24:07and then we uh you know kind of read from left to right let me write down the numbers this

24:12time for

24:13fun if we read the numbers from left to right physically without kind of like following edges

24:19or anything we just scan our eyes from left to right we can see that we have an ascending list

24:24if we supported duplicates it would be okay to just see a non-decreasing list

24:30but we see an increasing list or an ascended list ascending list

24:37okay whoops this is the slow part okay notice how the numbers increase from left to right

24:45so this is actually a binary search tree and um i don't know about you but i think i need

24:52to like

24:53you know get a snickers or something right now because uh this video has been going on for longer than

24:57i

24:58wanted it to go on so we've defined a binary search tree in future videos we'll talk about how to

25:03add

25:04nodes into a binary search tree how to build the tree what's the time complexity of the tree in

25:08various operations deleting nodes from a tree terminology like what are these nodes called

25:13things like that so anyway thank you so much for for watching i hope you learned a little bit of

25:19stuff

25:19and had a little bit of fun i'll see you at a later date in time just kidding

25:33hey everybody thanks for watching this video again from the bottom of my heart i really appreciate it

25:37i do hope you did learn something and have some fun if you could do me a please a small

25:42little favor

25:43could you please subscribe and follow this channel or these videos or whatever it is you do on the

25:49current social media website that you're looking at right now it would really mean the world to me

25:53and it'll help make more videos and grow this community so we'll be able to do more videos longer

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

26:04kindness and uh and subscribe you know sometimes i'm sleeping in the middle of the night and i just wake

26:10up

26:10because i know somebody subscribed or followed it just wakes me up and i get filled with joy that's

26:14exactly what happens every single time so you could do it as a nice favor to me or you could

26:19you control me if you want to just wake me up in the middle of the night just subscribe

26:22and then i'll i'll just wake up i promise that's what will happen also uh if you look at the

26:28middle

26:28of the screen right now you should see a qr code which you can scan in order to go to

26:32the website which i

26:33think is also named somewhere at the bottom of this video and it'll take you to my main website where

26:38you can

26:38just kind of like see all the videos i published and the services and tutorials and things that i

26:42offer and all that good stuff and uh if you have a suggestion for uh uh clarifications or errata or

26:52just

26:52future videos that you want to see please leave a comment or if you just want to say hey what's

26:56up

26:57what's going on you know just send me a comment whatever i also wake up for those in the middle

27:01of

27:01the night i get i wake up in a cold sweat and i'm like it would really it really mean

27:06the world to me i

27:07would really appreciate it so again thank you so much for watching this video and um enjoy the

27:13cool music as as i fade into the darkness which is coming for us all

27:23so

27:31so

27:33so

Category

Transcript

Comments

Recommended