# Binary Search Trees: Part 2

Published on May 6th 2023Duration: 56:43Watch on YouTube

Carol and I continue our lesson on binary search trees. This time we focus in on how to add a new entry to the tree.

## Transcript

The following transcript was automatically generated by an algorithm.

• 00:00 : there's a mountain and you're skiing
• 00:02 : down the mountain
• 00:04 : you're not going to explore multiple
• 00:07 : paths because the only way is down so
• 00:10 : you only Traverse one of the many paths
• 00:14 : one of the trails I like this analogy I
• 00:18 : want to go skiing but
• 00:23 : so I guess we left off at
• 00:28 : we've seen how a binary tree can be
• 00:33 : traversed
• 00:35 : how you can add insert a new node into a
• 00:39 : binary tree then how you can find an
• 00:42 : existing value in a binary tree
• 00:46 : um
• 00:47 : and
• 00:49 : we haven't completed the crud I think we
• 00:53 : kind of we kind of did a hand wavy way
• 00:56 : of seeing how to create a new node
• 01:00 : um
• 01:03 : hold on
• 01:07 : um
• 01:08 : um oh and we didn't write down we talked
• 01:13 : um I didn't write down
• 01:16 : the algorithm but the algorithm is
• 01:20 : basically
• 01:21 : you you kind of walk through it but
• 01:24 : basically the algorithm is
• 01:28 : um
• 01:30 : while
• 01:32 : while uh
• 01:35 : haven't well uh current node
• 01:40 : is
• 01:42 : not null
• 01:45 : and
• 01:48 : uh
• 01:50 : node value
• 01:52 : is not equal to the Target let's say
• 01:55 : like we haven't found it yet
• 01:58 : um
• 02:00 : then
• 02:06 : then if the current node
• 02:09 : is if the note that's called it no value
• 02:14 : if the note value
• 02:16 : England language it might be like
• 02:18 : current note that value or something if
• 02:21 : no value is if the target
• 02:24 : is
• 02:26 : is greater than the note value
• 02:31 : um
• 02:33 : then you then current node
• 02:39 : is the new
• 02:43 : dot is equal to the right child let's
• 02:47 : see
• 02:49 : uh else if Target is less than the no
• 02:53 : value then current node
• 02:56 : becomes the left child
• 02:59 : right that that that's more or less the
• 03:02 : algorithm
• 03:03 : there might be some details I'm missing
• 03:05 : but that's the idea and what is the Big
• 03:09 : O of this algorithm
• 03:11 : oh and and at the end if
• 03:14 : uh if they match or else then they match
• 03:21 : math
• 03:23 : uh well actually else it's not a match
• 03:28 : yet because the current note might be
• 03:30 : null
• 03:31 : so
• 03:33 : ah I'll just hand wave that as if Target
• 03:37 : is equal to no value then return current
• 03:43 : node let's say and then if you fall out
• 03:46 : of all of that
• 03:49 : uh
• 03:50 : else if
• 03:52 : no
• 03:54 : is no
• 03:57 : then return
• 03:59 : something like this sure
• 04:02 : um
• 04:04 : um it's actually a good exercise to code
• 04:07 : this up in whatever language you're
• 04:10 : comfortable with
• 04:12 : um but um
• 04:14 : I guess the what what is the big goal of
• 04:17 : this algorithm to retrieve a node in the
• 04:20 : in the binary tree I'm trying to think
• 04:23 : I'm going to try to think out loud on
• 04:25 : this one because
• 04:27 : I don't think it's
• 04:29 : Big O of in because
• 04:34 : is it Big O of like half of n because
• 04:37 : it's we're splitting everything in half
• 04:39 : in time like my where my brain is going
• 04:42 : is kind of like I know it doesn't it's
• 04:45 : not
• 04:46 : gonna grow
• 04:47 : in quite in step with the length or the
• 04:51 : size of our binary search trade but it
• 04:53 : is going to grow if we have a much much
• 04:56 : larger tree it's going to be larger than
• 04:59 : if we have a small tree but by but I
• 05:03 : Thinking by
• 05:04 : path
• 05:08 : try what by house
• 05:11 : by half it's a half of in I I don't
• 05:14 : think that's right actually
• 05:16 : um what is it oh is it the log yeah okay
• 05:22 : yes
• 05:24 : um that's the one
• 05:26 : um right so
• 05:30 : it it's login
• 05:33 : um
• 05:35 : and I would like to illustrate why
• 05:38 : um okay that would probably be good
• 05:41 : um so yeah the the bigger retrieval is
• 05:47 : the way to see why
• 05:51 : is this tree structure let's say you
• 05:54 : have a fully balanced oh it only works
• 05:56 : if it's a fully balanced tree if it's a
• 06:00 : completely unbalanced tree such as this
• 06:03 : one
• 06:04 : then it will be a big O of n
• 06:06 : because
• 06:08 : um because that's just like a linked
• 06:10 : list and you have to Traverse the whole
• 06:11 : link list sure uh so
• 06:15 : um but similarly to the binary search
• 06:20 : scenario
• 06:23 : um with each additional
• 06:25 : step we take and when I say step I mean
• 06:29 : the number of iterations of this while
• 06:31 : loop right uh with the with the binary
• 06:34 : search it was also like a loop right you
• 06:37 : you you go in a loop and in enter each
• 06:41 : iteration of the loop you shrink the
• 06:43 : search space in half right correct yeah
• 06:46 : so and we we call that the number of
• 06:49 : steps you take
• 06:51 : um so I use the word step here
• 06:54 : to mean each iteration of the loop
• 06:58 : uh and and in the case in in the case of
• 07:02 : the binary tree each step you take
• 07:04 : you're traversing down a level in the
• 07:07 : tree right yeah right like the first
• 07:10 : step you take you start from the root
• 07:12 : and then Traverse down one level to each
• 07:16 : child one of its children
• 07:19 : and so forth
• 07:21 : um so what I want to say is
• 07:25 : um
• 07:27 : um and just for succinct yes I uh I'm
• 07:31 : not going to draw the circles anymore
• 07:33 : um so
• 07:37 : um
• 07:38 : so like we have
• 07:41 : I've written out
• 07:45 : I want to draw a fully
• 07:50 : um
• 07:52 : balance and
• 07:55 : full tree
• 08:01 : oh hold on I messed up that that
• 08:04 : shouldn't be a four
• 08:06 : that should be like a nine or something
• 08:12 : eight
• 08:15 : data so
• 08:18 : um you can actually already kind of see
• 08:20 : the signs of uh
• 08:24 : of the exponential going on here because
• 08:28 : um
• 08:29 : if you count how many uh things are at
• 08:34 : each level
• 08:36 : so level one
• 08:39 : we have uh one node
• 08:42 : uh level two we have two notes
• 08:48 : and level three we have four notes now
• 08:52 : each time we're doubling right yes
• 08:55 : and if you go to level four we're gonna
• 08:58 : get eight notes and then sixteen notes
• 09:01 : and so forth
• 09:02 : so this is so the um
• 09:09 : so
• 09:10 : um the number of nodes
• 09:14 : there will be so the number again we're
• 09:18 : assuming a fully
• 09:21 : balanced tree
• 09:23 : and this may not always be the case so
• 09:26 : I'll caveat that
• 09:29 : um
• 09:29 : but we're if we assume the fully
• 09:31 : balanced tree
• 09:33 : then the number of elements that will be
• 09:36 : in a tree of level n
• 09:41 : it's like so the question is how many
• 09:45 : elements are in a
• 09:48 : fully balanced
• 09:52 : tree
• 09:54 : uh having n levels
• 09:59 : what was the answer to that
• 10:02 : so this is where my um my bad math
• 10:05 : skills are going to show themselves but
• 10:07 : we already have the first three levels
• 10:09 : calculated yeah but but as a formula
• 10:12 : yeah exactly it's a formula so it's like
• 10:15 : it's like
• 10:17 : okay so we don't know what n is
• 10:20 : we're like solving for n like n is
• 10:24 : unknown
• 10:26 : um but it should be
• 10:30 : so I know every every time we're
• 10:32 : doubling it every time we go through a
• 10:34 : level
• 10:35 : so what's the formula going to be if
• 10:39 : that's out
• 10:43 : ins
• 10:44 : Square it's not N squared
• 10:48 : I mean that's it's n Square for each
• 10:50 : level we go down correct but we don't
• 10:53 : know but we don't know how many levels
• 10:54 : we have
• 10:55 : uh right uh this might help uh if we um
• 11:01 : if we for now we'll discard level one
• 11:05 : that at level two
• 11:08 : we have two
• 11:11 : and then at level three I see the
• 11:14 : pattern I have two times two
• 11:16 : and then level four we have two times
• 11:18 : two times two
• 11:20 : and then level five we have two times
• 11:22 : two times two times two uh five times
• 11:25 : Etc
• 11:30 : so do you multiply two by itself
• 11:34 : uh that many times
• 11:38 : um and so that's an exponent certain
• 11:41 : exponential so that means it's two to
• 11:44 : the
• 11:45 : n
• 11:47 : okay
• 11:48 : two to the n
• 11:54 : 2 to the n
• 11:59 : and if I ask the inverse question now
• 12:04 : um
• 12:08 : how many
• 12:09 : how many
• 12:12 : levels
• 12:14 : are in a tree
• 12:18 : in a fully
• 12:20 : balanced tree
• 12:23 : that contains
• 12:25 : uh
• 12:27 : uh let's not use n this time that
• 12:29 : contains e elements
• 12:35 : what's the answer to that that's the
• 12:38 : exactly inverse question right
• 12:41 : is and so an element is
• 12:44 : just a number
• 12:46 : or it does it could be a person it could
• 12:49 : be anything but um yeah in simple
• 12:52 : example is a number
• 12:55 : so it's going to be
• 12:57 : the number
• 13:00 : to five we're going to be dividing
• 13:04 : by n
• 13:07 : no that's not right I'm sorry I told you
• 13:09 : my math skills are Rusty I need to I
• 13:11 : need to do some studying up here it's
• 13:13 : going to be the number of elements okay
• 13:14 : we've got the number of elements
• 13:19 : this is the well this is the exact
• 13:23 : inverse of
• 13:25 : um of the exponent the exponent so it's
• 13:29 : like
• 13:30 : before I was saying
• 13:34 : um
• 13:34 : if
• 13:36 : if the tree has
• 13:38 : three levels
• 13:41 : then you're gonna say
• 13:45 : um
• 13:46 : well to to the uh it's actually two
• 13:50 : minus two at two to the N minus one
• 13:54 : actually
• 13:56 : uh because
• 13:59 : um if it has one level
• 14:04 : um
• 14:05 : well okay
• 14:08 : um
• 14:09 : I don't want to confuse you too much but
• 14:11 : but for for level one
• 14:14 : it the answer is one because there's
• 14:17 : only one node oh hold on this is wrong
• 14:21 : sorry
• 14:23 : um
• 14:25 : how many elements are in uh
• 14:29 : okay so if if it's um
• 14:38 : I'm confusing two issues one one is how
• 14:42 : many elements are in that level
• 14:44 : but another is how many elements are in
• 14:48 : the entire tree
• 14:50 : and those are slightly different so
• 14:54 : level three there are four elements you
• 14:57 : can see these four numbers yeah
• 15:00 : uh but in a tree in the whole tree there
• 15:03 : are actually seven elements
• 15:08 : seven total let's say because we're
• 15:11 : adding up these three here as well right
• 15:15 : um and then there's a in level two if we
• 15:18 : don't count the third level we just
• 15:21 : pretend it's a tree that only has these
• 15:24 : three things then there's three total
• 15:27 : and then level one there's just one tool
• 15:32 : I kind of skipped over that and it tend
• 15:36 : to go too fast
• 15:38 : um and if we did one more level then the
• 15:43 : level four
• 15:46 : I'm not gonna draw them out just because
• 15:48 : it's tedious but level four would have
• 15:50 : eight elements
• 15:52 : but the total number would be eight plus
• 15:57 : which we would have fifteen dollar
• 16:01 : um Etc
• 16:03 : and the way you well the pattern
• 16:09 : might emerge
• 16:11 : um you might see it if you just look at
• 16:14 : it and realize that
• 16:16 : the other element like if you count the
• 16:19 : number of elements in a level say the
• 16:22 : third level there are four
• 16:25 : um the other elements in the tree is
• 16:29 : always going to be one less than the
• 16:32 : number of elements in that level
• 16:35 : um
• 16:36 : like this four and there's three from
• 16:40 : from the top
• 16:41 : and then if if it if it's level four and
• 16:44 : it has eight
• 16:46 : then
• 16:47 : there's going to be seven above it I see
• 16:52 : um
• 16:53 : and and so forth there might be multiple
• 16:57 : ways to arrive that at that conclusion
• 16:59 : but basically
• 17:01 : uh you might come up with the answer
• 17:04 : that it is you you double the number of
• 17:09 : uh elements at that level and then U
• 17:12 : minus one
• 17:18 : okay
• 17:19 : so we can do that as a four yeah I'm I'm
• 17:23 : very very uh slow with math I promise
• 17:26 : I'm sorry sorry Toby that's not helpful
• 17:28 : for this you know click on the feet I
• 17:30 : usually have to write it out and think
• 17:31 : and that's not a good thing but I have
• 17:33 : room to improve
• 17:34 : um let's see okay so that formula is
• 17:37 : makes a lot of sense so let's say we
• 17:40 : have okay how many levels are in a fully
• 17:42 : balanced tree that contains e elements
• 17:44 : we know the number of elements
• 17:46 : so we
• 17:49 : can
• 17:51 : so if if we had a lookup table yes then
• 17:55 : then it would just be a lookup to answer
• 17:57 : this question right
• 18:00 : if I wrote all of these things down
• 18:03 : sure then you you'll be like okay it
• 18:06 : contains eight elements okay
• 18:09 : 15.
• 18:11 : how many levels no it contains uh 15
• 18:15 : elements because this this 15 is what
• 18:18 : we're trying to match so right if it
• 18:20 : contains 15 elements then there needs to
• 18:24 : be four levels if it contains uh Seven
• 18:27 : Elements then there needs to be three
• 18:30 : levels
• 18:31 : um if it's greater than seven but uh
• 18:36 : less than 15
• 18:38 : it still needs to be at least four
• 18:40 : levels because there's some spilling
• 18:42 : over from level three
• 18:47 : so and and that uh the thing that
• 18:51 : expresses this relationship it's the
• 18:54 : inverse of this
• 18:55 : to uh uh to the end power
• 19:00 : uh equation
• 19:02 : and the inverse of the exponential
• 19:05 : equation
• 19:07 : is what do you remember okay because
• 19:11 : this we looked at this last time and we
• 19:14 : were like well
• 19:16 : if you plot this
• 19:19 : thank you the log the log is the inverse
• 19:23 : yes I do remember that sorry okay yeah
• 19:25 : yeah so so the the the exponential it
• 19:29 : looks like this yeah and then if we just
• 19:31 : flip this and then turn it 90 degrees it
• 19:35 : it looks like that
• 19:37 : so so this guy
• 19:40 : is the exponential and uh that other guy
• 19:44 : is the lock
• 19:46 : got it okay
• 19:48 : okay and and there are inverses of each
• 19:51 : other so so yeah so
• 19:54 : yeah so
• 19:56 : so this would be log a log base 2
• 20:01 : because we had the base of the exponent
• 20:04 : was two log base 2 of uh well e
• 20:09 : um
• 20:10 : so yeah log base 2 of e so
• 20:14 : um and this minus one that's just to be
• 20:18 : precise right but again when we're doing
• 20:21 : Big O we don't care about the little
• 20:23 : details like that so so at the end we're
• 20:27 : just gonna say oh it's a it's a log
• 20:29 : function
• 20:31 : um and therefore
• 20:33 : uh if you look at what the algorithm is
• 20:36 : doing
• 20:39 : at most it's going to travel the entire
• 20:43 : height of the tree right
• 20:47 : it's it's basically it's there's a
• 20:50 : mountain and you're skiing down the
• 20:52 : mountain
• 20:53 : through through one very narrow path
• 20:58 : you're not going to explore multiple
• 21:00 : paths because the only way
• 21:04 : is down is downwards so you'll only
• 21:08 : Traverse one of the many paths on the
• 21:12 : mountain oh one of the trails I like
• 21:15 : this analogy of skiing oh I want to go
• 21:18 : skiing but um
• 21:21 : um but yeah and and that is basically
• 21:23 : the height of
• 21:25 : the mountain or the tree
• 21:28 : uh and and now the height of the
• 21:31 : mountain right that's the number of
• 21:34 : levels of the tree
• 21:36 : and that is log
• 21:38 : base 2 of E
• 21:40 : and therefore
• 21:42 : uh the amount of iterations of this
• 21:46 : while loop that will have to do
• 21:49 : is at most the height of the tree
• 21:52 : and that is a log of N and therefore
• 21:56 : this algorithm's runtime is at worst
• 21:59 : Pico of log of n
• 22:01 : if we have a balanced strength I want to
• 22:04 : put a pin back in that and I feel like
• 22:05 : we'll Circle back around to it but yeah
• 22:09 : yes if if tree is balanced
• 22:15 : see like how important that is yeah
• 22:17 : exactly
• 22:19 : um
• 22:20 : so
• 22:22 : um and okay I think that was really good
• 22:25 : to like
• 22:29 : get into the details of that and uh see
• 22:33 : that
• 22:38 : nerd well
• 22:39 : creating a note is actually just binding
• 22:43 : the place where you're supposed to be
• 22:47 : and then and then
• 22:51 : and then sticking it
• 22:53 : uh under the node right so
• 22:58 : it'll be similar so basically spine
• 23:02 : uh the number you are closest to more or
• 23:08 : less
• 23:09 : which is going to be bigger of login
• 23:14 : uh using same same as retrieve
• 23:21 : and then you're just gonna
• 23:25 : or to closest to or or
• 23:28 : at the bottom of the tree
• 23:34 : uh closest to which
• 23:37 : um
• 23:42 : let me think
• 23:48 : I'm thinking about the case of a
• 23:50 : collision and what to do in that case
• 23:53 : um yes
• 23:55 : I also had that question okay so if
• 23:58 : there's no Collision then it'll
• 24:01 : definitely go to the to a place where
• 24:05 : you're gonna be left with a no pointer
• 24:09 : right and then you can just say oh you
• 24:12 : oh you already had a null pointer so let
• 24:15 : me just
• 24:16 : stick myself in here where it used to be
• 24:19 : not okay
• 24:21 : um so maybe I should write this all out
• 24:24 : then
• 24:25 : um so
• 24:27 : while current node
• 24:31 : um
• 24:32 : is not no
• 24:36 : um
• 24:37 : if
• 24:38 : Target is greater than node value
• 24:43 : then
• 24:44 : current
• 24:46 : node is Right child
• 24:51 : uh if Target is less than node value
• 24:57 : and current node is left child
• 25:02 : who else if
• 25:05 : node is the node value what do you do
• 25:08 : oops
• 25:13 : um what do you do in this case
• 25:15 : um
• 25:16 : let me think I think you can
• 25:19 : choose to go either left or right I
• 25:23 : believe
• 25:24 : let me see what would happen
• 25:28 : huh
• 25:32 : I think that can work
• 25:35 : either way yeah in in some system like
• 25:38 : you depends on your application so for
• 25:42 : some applications you don't want to
• 25:44 : allow duplicate values at all sure like
• 25:47 : like well this needs to be a primary key
• 25:51 : right uh we we don't want any duplicates
• 25:54 : so maybe you just throw an error but
• 25:56 : let's but if you did want to allow
• 26:00 : duplicate values then
• 26:03 : like let's say we wanted to put
• 26:06 : the value 12 into this tree again
• 26:09 : and then you'll say like
• 26:12 : uh well 12 is equal
• 26:16 : um uh okay you can but we still have to
• 26:21 : put it in the tree somehow so I don't
• 26:23 : care I go left or go right you either I
• 26:27 : could see like you randomly choose but
• 26:30 : uh you could also just like
• 26:32 : deterministically say well if it's equal
• 26:34 : I also go left
• 26:37 : and then if you did go left
• 26:40 : then you end up putting the new 12.
• 26:46 : new 12.
• 26:47 : uh no the 12 will go oh it's greater
• 26:51 : yeah I'm sorry yeah yeah
• 26:53 : totally missing that it's
• 26:55 : yeah the new 12 will go here yeah and
• 26:58 : let's say if you wanted to put in 12
• 27:01 : again
• 27:02 : then you yeah go okay go left and then
• 27:06 : go right and then you go left and then
• 27:09 : the new 12 will go here
• 27:13 : Etc
• 27:17 : so you just will end up with a bunch of
• 27:19 : 12s that are clustered yeah but but you
• 27:23 : can only add things at the bottom of the
• 27:27 : tree in this oh not necessarily the
• 27:29 : bottom but you can only add things at a
• 27:31 : place where
• 27:34 : to there's a note that is a leaf these
• 27:37 : are called leaves okay like they are
• 27:40 : they don't have bow tie of their
• 27:43 : um children's set to something already
• 27:46 : so these guys are called so you can only
• 27:49 : add yourself under a existing leaf
• 27:54 : and so so I guess
• 27:57 : if we go with that approach then you can
• 28:01 : say if
• 28:04 : you know if it there then also go to the
• 28:07 : left
• 28:10 : left or maybe like this is less than or
• 28:14 : equal to then we go to the left
• 28:18 : and then else
• 28:21 : uh
• 28:22 : uh no there's no else because
• 28:25 : um
• 28:28 : because we covered all the cases it's
• 28:31 : either greater than or less than or
• 28:33 : equal to and if it's a null then we're
• 28:36 : gonna jump out of the while loop
• 28:39 : uh
• 28:42 : uh and then I guess at the point at
• 28:44 : which
• 28:45 : you jump out of the while loop
• 28:50 : well that's kind of a problem actually
• 28:53 : we're gonna need to
• 28:58 : no I don't want to expose too much
• 29:01 : of the nitty-gritty but sure parent will
• 29:05 : need to have a parent note of the
• 29:08 : current note maybe we can in some tree
• 29:11 : implementations
• 29:13 : you can get you can
• 29:16 : get at the parent node if you have the
• 29:18 : current node I see
• 29:21 : let's let's just hand wave and say you
• 29:24 : can do that
• 29:25 : but although you if you couldn't do that
• 29:28 : you could just keep track of what the
• 29:30 : parent note was while you're doing this
• 29:32 : Loop stuff right true true yeah so I'm
• 29:36 : just gonna say parent no then parent
• 29:38 : node
• 29:40 : uh
• 29:43 : uh oh shoot
• 29:50 : but I didn't I don't know which whether
• 29:53 : I went left or right from the parent
• 29:56 : node
• 29:57 : so
• 29:58 : so like Japan uh
• 30:02 : uh left or right child
• 30:05 : will equal to a new node
• 30:09 : with the Target value
• 30:14 : um and I'm hand waving that
• 30:17 : uh the either left or right trial
• 30:20 : depending on which direction I went down
• 30:24 : for the previous turn if that makes
• 30:26 : sense to get to the current node I think
• 30:29 : I'm sort of missing something I want to
• 30:31 : sort of talk through this create okay
• 30:33 : that you've you've laid out here okay so
• 30:38 : we we have to create a new note
• 30:41 : I think maybe we
• 30:44 : okay maybe we should actually code it
• 30:46 : but uh yeah yeah talk through it first
• 30:49 : okay so we're trying to create a new
• 30:53 : node that's the objective okay so we're
• 30:56 : going to
• 30:57 : enter into a while loop what condition
• 31:00 : is if the current node
• 31:03 : is not null we we want you know to
• 31:06 : Traverse until we get to it null node
• 31:10 : yep the way we're going to do that is
• 31:13 : with our left foot let's let's set up
• 31:17 : the current note first so at the
• 31:19 : beginning we're going to say current
• 31:21 : node is equal to the root of the tree
• 31:28 : yep got it well that new
• 31:33 : Target
• 31:34 : but wait we have a Target what is the
• 31:37 : target this target was passed into the
• 31:39 : function okay Target is the node the
• 31:42 : value we want to create yeah
• 31:46 : maybe I should call it new value create
• 31:49 : maybe use the new
• 31:53 : value
• 31:55 : yeah that's that's good that's more
• 31:57 : clear
• 31:59 : okay so if the new value is greater than
• 32:02 : we're going to
• 32:04 : fall down into the right child if it's
• 32:06 : equal to or less than
• 32:10 : right yeah we're going into the left
• 32:14 : child
• 32:15 : um
• 32:16 : so we're going to keep doing that keep
• 32:18 : keep you know following that pattern of
• 32:20 : we go left or we go right based on our
• 32:22 : condition until we get to a null
• 32:31 : when that happens yeah because of this
• 32:35 : once we're at our null node we fall out
• 32:39 : of the while loop like you said and then
• 32:43 : we write our new value
• 32:47 : and replace replace the null value with
• 32:50 : our new value guess what I'm
• 32:53 : wanting to make sure I'm understanding
• 32:55 : is sort of what you're talking through
• 32:57 : here
• 32:59 : we need to understand our relationship
• 33:01 : to our parent node at this point there's
• 33:04 : a gap yeah we need to know whether I am
• 33:08 : the current node is the left child or
• 33:12 : the red child of the parent node
• 33:14 : oh well but but the current note is null
• 33:17 : that's the problem the current node is
• 33:21 : null because we already fell out of the
• 33:24 : while loop
• 33:26 : so so that that's the case where so this
• 33:30 : would be like we try to add 12 and then
• 33:34 : we go here and we go here we go here and
• 33:36 : then we go here
• 33:38 : to the left of the last 12. right and
• 33:42 : and then the current node is no because
• 33:44 : the last 12 has no left child currently
• 33:49 : and then we we're going to want to
• 33:52 : take the parent node and set its left
• 33:55 : child
• 33:56 : to the new node we're going to create
• 33:59 : for the tree
• 34:03 : so that's more or less what I'm saying
• 34:05 : so it it depends on whether we took the
• 34:09 : right uh
• 34:11 : path or the left path at the previous
• 34:15 : term
• 34:18 : so do we need to know hey I took the
• 34:21 : right path or hey I took the left path
• 34:22 : yeah so so one way to do it might be
• 34:26 : like we just keep a little Boolean
• 34:30 : left or right yeah
• 34:33 : and it doesn't matter what it starts off
• 34:36 : with uh
• 34:39 : Boolean
• 34:41 : and then yeah if we took the right side
• 34:44 : we'll say
• 34:46 : left or right oh I'm gonna call it make
• 34:49 : it a string actually
• 34:52 : okay
• 34:53 : I'll make it empty left or right if we
• 34:57 : took the right side we'll set it to
• 35:01 : left and now I said
• 35:04 : the left if right and then we at the end
• 35:08 : we can do a little if statement
• 35:11 : here to say if we previously took the
• 35:15 : left then we'll set parent note
• 35:17 : left trial to the new node but if we
• 35:20 : went right then we'll set turn no to
• 35:23 : right child instead
• 35:26 : something like that
• 35:27 : but I'm just trying to wrap my mind
• 35:29 : around why why this is necessary like I
• 35:32 : I I I understand that we need to know
• 35:35 : did we go left or right but why why do
• 35:38 : we need to know that why wouldn't we
• 35:39 : just either go left or right and then
• 35:41 : put the value in that place so oh the
• 35:44 : reason is because
• 35:45 : um let's say you have
• 35:49 : um let me see
• 35:51 : um
• 35:52 : let's say
• 35:57 : we had a value here
• 36:02 : to the right of 20 let's say 25 we had
• 36:07 : 25 here okay
• 36:10 : so 20 has a right child but no left
• 36:13 : child
• 36:15 : so and we want to add
• 36:18 : 18. okay so we're gonna come down here
• 36:22 : and we're gonna
• 36:24 : hit uh
• 36:26 : to hit this in this spot here
• 36:32 : um and we're gonna end up with the
• 36:35 : current node is null
• 36:38 : always gonna be no at the end of that
• 36:42 : while loop
• 36:44 : um and we're gonna know the parent node
• 36:46 : of the null is 20.
• 36:50 : uh but we we're gonna want to know to
• 36:54 : set the new note at the left child of 20
• 36:57 : and not the right child of 20 because
• 37:00 : the red child of 20 actually has
• 37:02 : something in it
• 37:03 : and if we set the red tile of 20 we're
• 37:06 : gonna replace the existing thing
• 37:09 : that
• 37:11 : that is 25.
• 37:13 : okay
• 37:14 : I think that maybe this was part of the
• 37:18 : whole process all along that I just
• 37:19 : hadn't really thought through yet is
• 37:21 : like we always need to know hey did we
• 37:23 : go right or did we go left you always
• 37:26 : have to know that no matter what and I
• 37:28 : we I we just haven't really talked about
• 37:29 : it yet
• 37:31 : maybe I don't know
• 37:35 : okay I think it'll be it will help to
• 37:38 : actually write out the algorithm
• 37:41 : uh although we will have 15 minutes
• 37:46 : um
• 37:47 : so let me think
• 38:13 : let me
• 38:16 : um
• 38:19 : or it might be because if I write I'm
• 38:23 : not sure writing it out
• 38:25 : would necessarily clear it up for you
• 38:28 : either
• 38:30 : um because we would run that and then
• 38:32 : maybe it works
• 38:34 : and you're like okay but that doesn't
• 38:37 : necessarily illustrate it either
• 38:40 : um
• 38:41 : hmm
• 38:43 : that there's actually multiple ways of
• 38:45 : implementing this algorithm in the way
• 38:48 : the way I chose
• 38:51 : might not be the cleanest uh but that's
• 38:54 : just because
• 38:57 : um
• 38:58 : I haven't
• 39:00 : uh thought out all the different
• 39:03 : but I just haven't thought ahead sure um
• 39:06 : just I just went into it but um but I
• 39:11 : think in a way that's good too because
• 39:16 : like
• 39:18 : I want to show the naive way because the
• 39:23 : naive way is more easy to
• 39:27 : um understand intuitively
• 39:31 : um so yeah the naive way is sort of like
• 39:37 : there you can also do it with
• 39:41 : um the recursive function where
• 39:46 : um
• 39:47 : let me think
• 39:49 : in either case I think it might be worth
• 39:52 : it might help to visualize it as this
• 39:57 : like
• 39:59 : okay I'm gonna draw another tree
• 40:02 : okay and then and then I'm gonna show
• 40:04 : you what it would feel like like I want
• 40:08 : to try to illustrate what it feels like
• 40:12 : to be the program
• 40:15 : that that is actually uh doing this uh
• 40:22 : um
• 40:23 : okay you have so you have a treat
• 40:27 : um and you know uh throughout it
• 40:32 : uh maybe maybe I don't go out again I'm
• 40:35 : gonna uh it's actually not super easy
• 40:40 : to just
• 40:42 : can I just do like this hold on
• 40:50 : oh that'd be too simple you could just
• 40:52 : pick that up
• 40:54 : there you go
• 41:07 : it works
• 41:09 : uh okay so so
• 41:14 : can I like is there like uh pointer
• 41:18 : function or something
• 41:20 : I can select all these guys and move
• 41:23 : okay
• 41:24 : all right that works
• 41:26 : okay so this is the tree that we're and
• 41:30 : we're gonna try to add
• 41:33 : we're going to try to add a 7 into the
• 41:38 : tree let's say now
• 41:40 : for us humans we can see everything here
• 41:44 : right but for a
• 41:47 : for the program that's looking at it
• 41:50 : traversing down the tree it can only
• 41:52 : look at node by node
• 41:55 : so
• 41:57 : it's kind of like
• 41:59 : um
• 42:01 : it can only see this
• 42:04 : yeah
• 42:05 : right and it's not allowed to see the
• 42:09 : rest of the tree while it's doing it and
• 42:12 : when when it's looking at this it's
• 42:15 : saying well current node is
• 42:20 : uh six
• 42:23 : um
• 42:24 : so and and my and my new value is seven
• 42:30 : right so so it's like well is it
• 42:36 : good which way should I go should I go
• 42:38 : left or should I go right well in this
• 42:40 : case I should go right mm-hmm and if I
• 42:43 : go right
• 42:45 : now I'm looking at this right yeah and
• 42:48 : and the current node is going to update
• 42:50 : to nine
• 42:52 : and again which way should I go the left
• 42:55 : or right uh in this case I should go
• 42:58 : left left yeah I'm gonna move the four
• 43:02 : out of the way here
• 43:05 : so I'm looking at eight so now the
• 43:09 : current node is eight yep and then it's
• 43:13 : like should I go left or should I go
• 43:15 : right uh and in this case is smaller so
• 43:18 : we're gonna go
• 43:20 : to the left and there's nothing here
• 43:23 : so here where there's not and we
• 43:28 : were supposed to like notate it like
• 43:32 : like this sometimes yeah so I'm looking
• 43:36 : this is a null value
• 43:38 : and I want to basically when I see a
• 43:41 : null value then I know I should put
• 43:44 : myself here
• 43:45 : I should replace this null value
• 43:49 : with myself with my new value yeah well
• 43:51 : technically I have to like generate a
• 43:54 : new node first and then stick stick the
• 43:57 : new value inside the new node and then
• 43:59 : put it here but the problem is
• 44:03 : um the way of putting yourself
• 44:06 : in this place
• 44:08 : is you actually have to ask the parent
• 44:11 : note the eighth note
• 44:13 : hey can you
• 44:15 : make your left child refer to my new
• 44:20 : node
• 44:21 : so that's the problem
• 44:23 : right and if if when you're in this
• 44:27 : limited view
• 44:30 : if you don't have access
• 44:33 : to the parent node then you don't have a
• 44:36 : way
• 44:37 : of attaching yourself to the tree first
• 44:40 : of all which is why you need to have
• 44:47 : if you do get to this place
• 44:50 : um
• 44:51 : um and then secondly have an access
• 44:55 : enough because you need to know whether
• 44:57 : you should insert it yourself to the
• 45:00 : left or the right of the parent
• 45:04 : okay so it's like when you're
• 45:07 : the program and you're on eight your
• 45:10 : current note is eight
• 45:12 : you know I have a left path and a right
• 45:15 : path I can ski down here you do you say
• 45:18 : okay my new value is seven so I know I
• 45:21 : need to ski down my left path right then
• 45:24 : you get to the bottom of that and you
• 45:26 : have you have no more memory of hey am I
• 45:28 : on the left you're around the right
• 45:29 : exactly because you're there now that's
• 45:32 : exactly what it is so so what you could
• 45:34 : there's multiple strategies for how to
• 45:36 : do this like one strategy would be like
• 45:41 : well okay maybe instead of skiing down
• 45:45 : here to this no value I'm gonna do
• 45:48 : everything up here while I still can
• 45:52 : that's one strategy well that would mean
• 45:55 : you would add logic to say well if my
• 46:00 : left child is no then go ahead and stick
• 46:02 : it in there
• 46:04 : or if you choose to go right then
• 46:07 : instead of like moving to the moving the
• 46:11 : whole frame to the right or moving the
• 46:13 : whole frame to the left you're gonna say
• 46:15 : oh if the left side is null and you know
• 46:20 : then just stick yourself just change
• 46:23 : your left reference to that
• 46:25 : if you are planning to go left anyway
• 46:28 : and ins instead of moving the frame then
• 46:32 : just attach it yeah you're gonna need a
• 46:35 : couple more if statement to your code to
• 46:38 : do that right
• 46:39 : so it's a it's a trade-off
• 46:42 : um or
• 46:43 : what you could do is say
• 46:46 : uh you know what I'm gonna keep track of
• 46:49 : who my parent note is
• 46:53 : that can and if I am on this Frame then
• 46:56 : my parent node is nine right and I'm
• 47:00 : gonna also keep track of you know
• 47:03 : uh my how I got here uh
• 47:08 : so like relationship
• 47:12 : relation to parent
• 47:14 : is left
• 47:18 : and if I had those two pieces of
• 47:20 : information inside this Frame then I
• 47:23 : would know what to do then then if I
• 47:25 : move down to this Frame and then the
• 47:27 : current node was null
• 47:30 : and now I have the parent node and I
• 47:34 : have the relationship to parent is left
• 47:36 : then I know okay I should take my parent
• 47:40 : note and set its left child to the new
• 47:43 : note that I'm gonna create
• 47:47 : yeah I'm the I'm I'm understanding my
• 47:51 : brain's there finally
• 47:54 : so uh so that's uh
• 47:58 : that's uh I I think this yeah if this is
• 48:04 : this data structure
• 48:07 : uh yes it is it's kind of like yeah I I
• 48:10 : I'm envious of you
• 48:13 : it's like that to be seeing this for the
• 48:16 : first time
• 48:18 : um
• 48:18 : I do vaguely remember like the first
• 48:26 : and uh it was like really weird really
• 48:30 : kind of foreign to me
• 48:32 : uh but uh kind of interesting but I
• 48:36 : didn't totally get the implication of it
• 48:38 : either even after that entire course
• 48:41 : even after years later uh I didn't
• 48:45 : really get it
• 48:47 : um yeah
• 48:48 : yeah so far to me this is the coolest
• 48:51 : data structure we've looked at for some
• 48:53 : reason I just really like it I think
• 48:55 : it's very beautiful I think it it
• 48:57 : reminds me of
• 48:59 : it's like this intersection of of
• 49:02 : artistic and
• 49:04 : and very practical like I don't I can't
• 49:07 : even describe it but it's a really cool
• 49:09 : data structure I'm excited to to
• 49:11 : continue learning about it yeah yeah
• 49:13 : yeah we can go further
• 49:15 : um so since we only have a few minutes
• 49:17 : left I'm going to go uh just like Zoom
• 49:21 : back out a little bit and look at the
• 49:22 : big picture
• 49:24 : um and to say that
• 49:27 : I actually uh on my YouTube channel I
• 49:31 : previously did a
• 49:33 : uh
• 49:36 : did a video with huichi about how
• 49:39 : databases work okay and
• 49:43 : and um
• 49:47 : very very much related to this concept
• 49:51 : um although databases don't use binary
• 49:55 : trees
• 49:56 : they use something that's called a b
• 49:59 : tree
• 50:00 : uh
• 50:02 : that's almost a binary tree but uh but
• 50:06 : uh the concept of the vitri is is still
• 50:10 : similar to the binary tree it's just
• 50:12 : that each node in the tree
• 50:14 : the binary tree has a fan out of two
• 50:18 : whereas a b tree can have any amount of
• 50:21 : fan out
• 50:23 : ah so so a b tree can have each node
• 50:29 : let's say uh I have eight eight elements
• 50:34 : in each node of the tree
• 50:39 : and in a b tree I don't know they
• 50:42 : probably use some Power of Two
• 50:46 : like 8 16
• 50:48 : 32 64. stuff like that
• 50:53 : um so I have eight things in the tree
• 50:56 : and each thing has a number in it or or
• 50:58 : well usually it'll be a record of some
• 51:02 : sort that has additional information but
• 51:04 : it'll have a key and the key is the
• 51:07 : thing that we're gonna sort by right
• 51:11 : we're gonna use it to decide whether
• 51:13 : we're gonna go to the left or to the
• 51:15 : right
• 51:16 : but
• 51:19 : um let's say
• 51:20 : you know do you have a key of one
• 51:24 : and then
• 51:26 : five
• 51:29 : eight
• 51:34 : uh
• 51:36 : come on
• 51:37 : what's going on oh I don't have to do
• 51:39 : this I can just
• 51:41 : 12
• 51:43 : uh
• 51:45 : 30
• 51:47 : 40 50. uh and then you're gonna fan out
• 51:52 : basically
• 51:55 : do eight more of these guys
• 52:00 : and well I'm gonna run out of room
• 52:03 : because it it because there's like eight
• 52:06 : more of these guys and each one is Big
• 52:09 : right
• 52:10 : yeah interesting
• 52:13 : um
• 52:14 : and Etc uh okay it's gonna be too
• 52:18 : tedious for me to do sure but but you
• 52:20 : just yeah just imagine there's um eight
• 52:23 : more and then at the next level
• 52:26 : still will be uh eight times eight which
• 52:29 : is 64. so at level three there's already
• 52:33 : 64.
• 52:35 : eight cell boxes
• 52:38 : um
• 52:40 : and which means
• 52:42 : um which every level
• 52:45 : you're so so this would be like um
• 52:49 : eight to the n
• 52:51 : instead of 2 to the n
• 52:54 : so it um
• 52:57 : so if you have a tree of n levels you
• 53:01 : will have eight to the N Things
• 53:04 : have eight to the N uh notes in the tree
• 53:09 : um
• 53:12 : but each node actually has eight
• 53:15 : elements in it
• 53:17 : it's it's yeah so which means the amount
• 53:23 : although the amount of processing you
• 53:25 : have to do
• 53:26 : at each node is greater
• 53:29 : because you not only choosing to go to
• 53:33 : the left or right you're choosing
• 53:35 : between eight different paths to go down
• 53:39 : and in order to do that you're gonna
• 53:43 : the first cell and you figure out if the
• 53:45 : target is in between one and five
• 53:49 : and then you figure out if the target is
• 53:51 : in between five and eight until you hit
• 53:54 : the correct uh range and then once
• 53:57 : you've hit the range then you go down uh
• 54:00 : that
• 54:02 : that trail that okay yeah
• 54:06 : um so that's uh that's B trees but I
• 54:12 : think
• 54:14 : um maybe a good analogy to this is like
• 54:18 : uh in a library you organize things
• 54:22 : usually by the first letter right
• 54:27 : so you can imagine there's a shelf for a
• 54:31 : a shelf for B
• 54:33 : Etc right right and and those are your
• 54:35 : ranges at the top at the top level maybe
• 54:38 : the bin one is or the ace and Bin two is
• 54:43 : all the B's Etc and maybe some there's
• 54:46 : some letters that are not as popular so
• 54:49 : you jam multiple ones together or
• 54:52 : something like X Y is z
• 54:54 : can all go on that one x y z shelf or
• 54:58 : something like that
• 55:01 : um and so you organize them in ranges
• 55:05 : but but it could be when your library
• 55:07 : gets really big then
• 55:10 : instead of shelves
• 55:13 : you have sections and each section has
• 55:16 : multiple shelves in it right yes
• 55:19 : so you have instead of an a shelf you
• 55:22 : have an a section which is an entire
• 55:25 : room
• 55:26 : and then inside that room you have to
• 55:29 : stop stop uh organize it that's your
• 55:33 : level two right and then you and then
• 55:36 : you organize the shelves inside the a
• 55:39 : room by the second letter of the uh of
• 55:43 : the author's name or something like that
• 55:45 : right sure yeah and and that's kind of
• 55:49 : what you're doing with with the beach
• 55:51 : and even with the binary tree you're
• 55:53 : kind of doing it that way you're just
• 55:56 : saying like well everything that's
• 55:59 : like less than six it can go into this
• 56:03 : side of the building
• 56:05 : greater than six it can go to the other
• 56:07 : side of the building and then I'm gonna
• 56:10 : subdivide it's it's just because like in
• 56:13 : computers everything's more Dynamic than
• 56:15 : the physical space so you can just sort
• 56:19 : of reorganize things and change them
• 56:22 : very quickly and that's what the binary
• 56:25 : tree is doing
• 56:26 : but uh conceptually it's same as
• 56:30 : dividing up physical space and try to
• 56:33 : organize stuff within it
• 56:36 : cool I'll have to keep that in mind
• 56:38 : because that that conceptual analogy
• 56:41 : that's really helpful