Binary Tree Traversal: Part 1

In this session Carol and I work through how to traverse a binary tree, and we come up with an interesting result. Also, at the beginning of the video, we do an overview of the binary search tree series, and pose a challenge: to to do a range search with a binary search tree?

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : I just did that
00:03 : so the next operation is that so I'm not
00:08 : back to the has jobs condition actually
00:10 : I see okay yeah okay we're still in it
00:13 : we're still in the first iteration so so
00:15 : temporarily we're out of drops but we
00:18 : we're not done with this iteration of
00:20 : the loop so we could still have more to
00:22 : do
00:25 : I kind of wanted to do a sum up of
00:31 : um where this binary tree
00:35 : data structure fits in to
00:39 : I think we had like an original goal
00:43 : of yeah this phone book app
00:48 : do you remember this yeah yeah
00:52 : we were like saying oh we have a phone
00:55 : book app and we want it to be able to
00:59 : add an entry
01:01 : to it you know whenever we want
01:05 : um and we want to be able to retrieve
01:08 : a person's phone number by their last
01:11 : name
01:13 : um
01:15 : and we had these multiple attempts
01:19 : actually attempt one was like you just
01:23 : added new entries to the back of the
01:25 : array and then you search the whole
01:27 : array
01:28 : and that was not good enough because
01:31 : searching the whole array is bigger of N
01:34 : and and I said that I wanted everything
01:38 : to be fast right I want both inserting
01:42 : things and retrieving things
01:44 : to be fast
01:46 : uh uh and then we said that we will sort
01:50 : the array alphabetically by last name
01:55 : um but then the problem is when you try
01:58 : to insert new things into the array and
02:01 : keep it sorted that's Big O of n so that
02:05 : that also doesn't work
02:07 : and then we had attempt three
02:09 : which was we're going to use a hash
02:12 : table
02:13 : that's gonna use the last name of the
02:16 : person as the key
02:17 : right and then we can use that to look
02:20 : up the phone number and that will
02:21 : actually be fast in both cases so that's
02:24 : sort of the first winner
02:26 : uh because you know look inserting a new
02:30 : entry is bigger of one uh on average
02:33 : with a caveat but uh looking up is also
02:37 : a bigger of one
02:40 : um but then I said
02:43 : well okay it's still not good enough
02:46 : because
02:48 : what if I want partial matching they go
02:52 : what if I want to be able to write
02:54 : the first three letters of the last name
02:57 : and still be able to look it up fast and
03:00 : the hash table cannot do that
03:02 : and that's what brought us to the binary
03:05 : search tree
03:06 : so
03:08 : I just wanted to wrap that up
03:12 : a good uh tie-in to I had kind of not
03:16 : forgotten but it's good to bring my mind
03:18 : back to that that was the point of this
03:20 : yeah that's the whole point that's
03:22 : that's how I tried to
03:24 : um motivate the binary trick so so
03:28 : attempt number four of this thing
03:31 : let's put it over here
03:34 : okay so attempt for uh we're gonna build
03:37 : this phone book
03:39 : using a binary tree
03:41 : and so we're going to use a binary
03:44 : search tree
03:46 : to store
03:48 : um
03:50 : entries uh
03:54 : uh that contain
03:57 : last name
04:00 : and phone number
04:02 : okay
04:05 : so we're gonna use uh we're gonna use uh
04:09 : the last name as the key
04:13 : the key of the tree which means
04:16 : when we're doing comparisons uh while
04:20 : searching down the tree or we're we're
04:24 : doing comparisons because we're trying
04:25 : to look for a spot to insert a new entry
04:28 : we're going to compare the last name
04:31 : okay
04:33 : um so this means uh
04:39 : um
04:42 : but yeah to add insert new entries
04:47 : use the
04:49 : uh
04:51 : uh PST
04:53 : insertion algorithm
04:56 : and that's bigger of login
04:59 : right
05:00 : and then you know search for
05:04 : um
05:06 : exact
05:08 : match
05:10 : um
05:12 : you use the BST uh
05:15 : retrieve or search I guess algorithm
05:21 : which is also a bigger login
05:24 : um
05:25 : partial search
05:29 : um how do we do our source search in a
05:31 : tree we didn't actually talk about that
05:34 : but
05:36 : intuitively it should be possible
05:38 : because
05:40 : we have this tree
05:43 : arranged
05:45 : in this sorted way right
05:48 : um
05:49 : so
05:50 : uh
05:52 : maybe I should make room over here yeah
05:54 : let's there's more room over here so
05:57 : let's say I have
05:59 : um
05:59 : [Music]
06:02 : Jenny
06:06 : uh
06:09 : Jeff
06:14 : uh
06:17 : uh okay over here maybe is uh
06:23 : any
06:25 : uh
06:32 : Abby
06:34 : uh
06:37 : what's between Jeff and Jenny so between
06:41 : the bathroom and
06:46 : John
06:48 : John no because but no it has to be j-e
06:50 : Jake I can move stuff around though uh
06:53 : John so John John is gonna come after
06:57 : Jenny
06:59 : uh
07:01 : uh maybe
07:03 : uh okay would end up here
07:09 : the the baby Kenny can be over here
07:13 : you think this
07:15 : maybe add a couple more oh
07:18 : or maybe I do
07:21 : I add Jam
07:25 : that's another one uh but Jim would go
07:29 : here though
07:30 : so maybe
07:32 : [Music]
07:32 : um
07:34 : what's the correct I think would Jeff
07:37 : not be to the right of jam
07:40 : if you put Ginny back at the top and
07:43 : just back as the left child
07:46 : oh yeah because e is after a
07:49 : going on the second letter
07:54 : uh maybe I just
07:57 : uh
07:59 : okay oh I'll put
08:02 : oh here's a question
08:04 : if I put Jefferson
08:07 : where does he belong
08:10 : uh
08:12 : uh would he be coming
08:16 : Jefferson would be before Jenny right
08:20 : but after Jeff
08:22 : probably right F okay so we're going off
08:25 : the third letter between
08:27 : as as comes before n so Jeff and
08:30 : Jefferson would be above Jenny before
08:34 : right before yeah before before yeah
08:36 : sorry
08:41 : uh and
08:43 : I can put in Joan here I think
08:47 : I I want to double check though so I'm
08:50 : going to
08:53 : um
08:55 : I'm gonna bring up a show
08:59 : do I have
09:00 : um
09:01 : python in here
09:07 : I will install python really quick
09:15 : archery with names is such a um
09:18 : concrete example of like oh this is such
09:21 : a good job for computers because it's so
09:23 : hard even when it's like like you know
09:26 : all the rules of organizing by names it
09:27 : just it takes so much mental energy to
09:29 : be like okay wait which name is where
09:32 : yes so I I want to see like is two F
09:36 : greater than Jefferson or the other way
09:39 : around yeah no Jefferson it Jeff is
09:44 : less than Jefferson
09:47 : so we have it correct and Jenny should
09:50 : be greater than Jefferson I believe
09:54 : so Jenny less than Jefferson should be
09:56 : false because Jenny is greater than
09:58 : Jefferson okay so this is the situation
10:01 : I want
10:03 : um
10:06 : let's see
10:09 : so I guess my my thing about parts so
10:13 : searching is I want to there's a lot of
10:17 : Jace so so if I if I type you know I
10:20 : have a I have a search box
10:24 : in my app right last name
10:29 : and then I'm typing in it and I type J
10:33 : and then I want to see like a drop down
10:37 : right
10:38 : right that that'll give me all the J's
10:40 : uh
10:42 : I want to see a drop down
10:45 : they'll give me like jam or in order
10:48 : ideally
10:50 : yeah Etc but uh you know if I if I
10:54 : put Je
10:57 : then I should be getting Jeff
10:59 : Jefferson and Jenny
11:02 : yeah and if I type j-o I should be
11:05 : getting John and Joan uh I guess it
11:09 : technically Jones should come before
11:11 : John because John is to the left of John
11:15 : so that's what we want to do right uh I
11:19 : and I think intuitively
11:22 : the binary search tree will allow me to
11:25 : do this and not only that it will allow
11:28 : me to do this efficiently
11:31 : um
11:32 : because
11:34 : like like if I were thinking about okay
11:36 : Je
11:38 : it because intuitively it like like
11:42 : um
11:44 : you know how we we move this bar and
11:47 : then we just
11:49 : um to comb the tree from left to right
11:52 : like this so intuitively it's sort of
11:55 : like
11:56 : I just need to do this
11:59 : scan operation
12:02 : until we hit the first thing
12:05 : that matches our je prefix yeah and then
12:10 : once we hit that
12:12 : then we continue
12:14 : and everything we hit that still matches
12:17 : je we will print it out and then the
12:20 : first thing we hit that doesn't match je
12:23 : will stop right there
12:25 : right right that's all we have to do so
12:30 : uh
12:32 : so that there should be an algorithm
12:34 : that will allow me to do that
12:38 : um
12:41 : let's try to sketch that out that that
12:43 : would be like a very cool code challenge
12:46 : as as well
12:49 : um I think I I wonder like and that's so
12:52 : practical too I wonder if Lee code has
12:54 : that
12:55 : um
12:56 : so
12:58 : what would be the uh maybe just do
13:02 : pseudo code so we'll call this like
13:04 : maybe partial match
13:09 : search
13:11 : how will we do this so I have a question
13:15 : in my mind the the visual that you just
13:19 : showed that we've gone over before where
13:21 : you have the line and it's moving from
13:23 : the left to the right across the tree I
13:26 : guess this kind of gets into the tree
13:27 : traversal because my thought would have
13:30 : been oh we always start at the root of
13:32 : the tree and go down we're not going
13:34 : left to right oh yeah yeah yeah yeah
13:36 : maybe maybe we shouldn't do this one
13:39 : first maybe we should do the tree
13:41 : traversal and then come back to this
13:43 : partial because like there's information
13:45 : I don't have that's okay how do you do
13:48 : this yeah yeah that's a good because
13:50 : this is honestly this is kind of
13:52 : advanced so so I'm gonna put
13:55 : a question mark like this is where we're
13:59 : getting this is our goal right this is
14:01 : like the ultimate
14:03 : uh where the whole point of
14:07 : in a sense the whole point of binary
14:10 : trees is we want to be able to do to do
14:13 : this so stay tuned for next time but uh
14:16 : let's let's instead of doing this but
14:19 : this is such a cool problem
14:22 : um I I really like this and um
14:26 : the heaven
14:29 : nobody has taught me how to do this
14:33 : uh so like I I think somebody should
14:36 : should do that
14:37 : um
14:38 : but yeah so so
14:41 : instead of this partial match thing
14:43 : let's let's move
14:46 : let's go take a step back and say
14:50 : all right
14:54 : instead of trying to do a partial match
14:57 : let's just
14:58 : reverse the entire tree
15:02 : um leelana tree traversal
15:08 : um so let me ask you how to do this uh
15:12 : use your problem solving
15:14 : put on your problem solving hat so the
15:18 : first problem that I'm gonna post to you
15:21 : is just
15:24 : uh
15:26 : uh run every element
15:29 : in the tree I just want you to print
15:31 : every name in this tree how would you do
15:34 : that
15:37 : first
15:39 : where my brain immediately goes is kind
15:41 : of this idea of how are we moving how am
15:44 : I going to move through the tree and
15:46 : because it's just sort of two-sided or
15:49 : not sort of it is two-sided it's like
15:53 : okay well I have to start at the root
15:54 : and then it seems like
15:58 : I could either go down one side
16:02 : but we talked about before kind of
16:04 : working our way down and like choosing a
16:07 : path
16:08 : so let's say okay so I want to go I'll
16:11 : I'll put a pin for just a minute on
16:13 : actually printing the names and just
16:14 : talk about getting to each of the names
16:16 : so we start at Jenny we
16:19 : go to the left and we we arrive at Jeff
16:22 : now we have two possible paths we could
16:26 : go down and we actually ultimately want
16:28 : to go down each so what I'm wondering is
16:31 : do we just choose one
16:34 : and then we arrive at Jam but now I'm at
16:37 : the bottom so do I have to start back at
16:39 : the top remember the path I went and
16:41 : then go a different path
16:43 : or can I when I'm at the bottom can I go
16:46 : can I back up
16:48 : and go the opposite way but then how
16:50 : does how do I have memory of like
16:54 : which way I went okay I'm at Jam if if I
16:57 : hypothetically could get backwards and
16:59 : get to Jess which is my I have to store
17:02 : somehow like hey I've already been here
17:04 : so I've already been left now I have to
17:07 : go right so the word the word memory is
17:11 : uh very
17:12 : uh
17:13 : uh very important and uh and um
17:19 : yeah let's talk about that how do you
17:22 : remember where you came from essentially
17:24 : would it be like um some sort of data
17:27 : structure that's that's keeping
17:29 : breadcrumbs would I have something
17:31 : that's like okay like I started here and
17:34 : then I went here he and then slot three
17:38 : so yes yes so what would that data
17:41 : structure look like
17:46 : so let's say
17:49 : um
17:51 : let me try to illustrate this app so so
17:54 : basically
17:57 : I mean I'm sure you're gonna flips
18:00 : yes I do want an arrow that's true oh no
18:04 : okay whoa what happened
18:08 : okay mind of its own
18:12 : um let's just call this like current all
18:15 : right okay uh like I want a variable
18:18 : that's called current
18:20 : I thought the arrow oh it's a Bent Arrow
18:24 : okay oh there we go yeah that's what I
18:27 : want to see
18:28 : uh
18:30 : so so as let's say and I I like to be
18:35 : intentionally vague about what this
18:37 : algorithm or this code is going to look
18:39 : like so
18:41 : um so let's just say we have a variable
18:44 : called current all right
18:46 : um and
18:48 : when initially we're gonna Set current
18:51 : to root right so this is at the very
18:55 : beginning
18:56 : we're gonna do that uh which is Jenny
19:00 : and then later on we're probably gonna
19:03 : move current down the tree
19:06 : uh yeah yeah so the the statement that
19:10 : does that probably will look something
19:12 : like
19:14 : no current equals root dot left let's
19:18 : move this over here
19:20 : um
19:21 : the mother thing may have to happen
19:24 : um and then even later on you will end
19:28 : up with that
19:31 : um
19:32 : and
19:34 : so there's probably a loop or some other
19:38 : mechanism that makes that process repeat
19:42 : um
19:43 : but then
19:45 : maybe at some point you realize you're
19:47 : at the leaf so you're like well if root
19:51 : dot left is null
19:54 : done what do you do
19:57 : um do you uh are you gonna come back up
20:02 : to Jeff where is Jeff how do you this is
20:06 : what you were talking about how do you
20:08 : remember
20:09 : where you came from how do you get back
20:11 : to Jeff here
20:13 : yeah
20:14 : well one option and I'm
20:18 : the ultimate
20:21 : option that we want but I'm just sort of
20:22 : talking through what comes to my mind
20:25 : um one option is that in addition to
20:27 : storing current
20:29 : restore previous
20:31 : but that but that I mean I don't really
20:34 : love that I'm just it just kind of
20:36 : working through how my brain's thinking
20:38 : through this if we store previous every
20:40 : time it doubles every you know instead
20:44 : of just storing current and switching
20:46 : that we have to switch current and
20:48 : previous and we really only care about
20:51 : previous at the end we don't care about
20:54 : previous let's say this was a great big
20:56 : huge tree with many many layers it it's
20:59 : the only reason we're keeping up with
21:01 : previous is so that at the very end we
21:03 : can be like okay now I go back but okay
21:06 : also as I say that
21:10 : so so okay let's say we're able to go
21:13 : back to previous let's just assume we
21:17 : can do that
21:19 : um
21:20 : are we gonna do this
21:24 : are we gonna do this and then
21:28 : we'll head back up to here
21:33 : um and and then and then what I I guess
21:36 : the reason you want this is so that
21:39 : later on
21:40 : you can say current is equal to current
21:43 : oh this should not be root with your
21:47 : current equals current you want to be
21:49 : able to get to the right side right
21:51 : that's why you're coming back up you're
21:53 : going to be able to say current equals
21:55 : current dot right
21:58 : um now of course I do have to do that
22:00 : over and over again I have to do that
22:02 : for every layer to make sure I get every
22:04 : right side of every subtree yeah yeah
22:08 : but then
22:09 : so let's say that happens
22:14 : um so then I go uh and then and then at
22:18 : some point
22:20 : well at some point you you need to come
22:23 : back up yet again after after you're
22:26 : done with the right side
22:28 : and then maybe you're gonna do this
22:31 : again
22:32 : after you after you've done the right
22:35 : side maybe it's it maybe it's oh this is
22:38 : clearly this is not going to work
22:40 : because if I Nest the if statement
22:43 : then I mean I I can't have a number of
22:47 : nested statements that's the same as the
22:50 : height of the tree that won't work
22:55 : the height of the tree is dynamic so I
22:58 : can't but let's say I could if I could
23:01 : then
23:02 : you maybe you're like you're at
23:04 : Jefferson and you realize oh I looked at
23:08 : both the left and the right side and the
23:10 : right side is null so I want to come
23:12 : back up to Jeff so turn equals previous
23:15 : uh because previous is pointing to just
23:19 : um but now
23:21 : I want to point out another problem
23:24 : which is well Jeff is done with himself
23:29 : and all of his children so we want to be
23:31 : able to go back up to Jenny
23:34 : uh how do you do that yeah because we've
23:37 : lost that reference to the previous so
23:39 : do we need previous previous right yes
23:43 : in this if we were working off of this
23:45 : method we would we would need every
23:47 : every
23:49 : level has to have its previous
23:53 : that's true every level as if no when
23:57 : you say that every level
24:00 : has to have its own version of previous
24:05 : um
24:07 : like how can you get that how do can you
24:10 : get it how do you
24:12 : make it so that at every level
24:15 : it can have its own
24:18 : previous variable say or it just have
24:22 : some way of storing its own version of
24:25 : previous
24:29 : it's like you need to create another
24:30 : Tree on top of this tree
24:34 : best storing all of the metadata that
24:37 : you're traversing
24:40 : it is very much that that's true that's
24:44 : true uh
24:47 : um
24:50 : Maybe
24:52 : um to
24:54 : blow with that other tree look like
25:01 : what you're saying is very right
25:04 : that's very right at a um
25:08 : it's cool because
25:10 : um
25:16 : that connection is not often made
25:19 : but when you say it when you say that
25:23 : there's another tree that's mirroring
25:25 : this tree
25:28 : um
25:29 : but what do you think that other tree is
25:31 : gonna look like what what is that other
25:33 : tree
25:36 : that I'm still
25:38 : thinking about yeah but it's like
25:44 : um
25:47 : it's like every spot and may the more I
25:50 : think about it the more I'm like is it
25:52 : actually a separate tree or do we need
25:55 : to modify the things that are stored in
25:58 : this tree and I really don't know I'm
26:00 : really brainstorming I'm thinking out
26:02 : loud here because it's like a lot of fun
26:06 : so that's another Avenue too uh I'm
26:11 : blending ideas now
26:14 : they are related because
26:17 : um Yeah you mentioned
26:21 : multiple ways like you you likely you
26:24 : have on
26:26 : um the tip of your tongue
26:29 : um described like multiple ways uh
26:34 : uh that people have used to solve this
26:37 : problem so there's not just one solution
26:40 : um
26:41 : but yeah like like the one that involves
26:44 : maybe not modifying the tree exactly
26:48 : there's a very very simple way to solve
26:50 : this previous problem
26:53 : um if we had only maintained
26:58 : um a pointer
27:00 : that can allow a child
27:03 : to get at its parent
27:05 : then that very simply solves everything
27:08 : so like
27:11 : so
27:12 : um
27:14 : so like we so far we've said like the
27:18 : each node has a left and a right right
27:21 : that implies that like we're you know
27:25 : we're pointing this way
27:28 : and we're pointing this way
27:30 : but ah but so we talked about last week
27:34 : I think yeah yeah yeah yeah the double
27:37 : the double arrow means yeah well maybe
27:40 : just can also point to Jenny too why not
27:45 : so uh and that's a that's an
27:48 : implementation Choice
27:49 : um
27:50 : uh this is not often done but sometimes
27:55 : it is done like in a lot of UI
27:58 : Frameworks uh this is done
28:02 : but I don't think react does this uh but
28:05 : but uh
28:07 : the Dom the dumb does do this which okay
28:12 : would enable you to say
28:16 : um earn equals current dot parent
28:20 : and you immediately get back to your
28:23 : parent
28:25 : s so so that actually solves it very
28:28 : simply uh I guess the thing that
28:32 : the cost of doing this is uh well you're
28:36 : adding new notes to the tree you have to
28:39 : also make sure you maintain this parent
28:41 : link as correct
28:45 : and also I guess you use a little bit
28:47 : more memory to just store that link it's
28:50 : not a lot really it's fine oh I I guess
28:54 : that there's another
28:56 : potential Hazard is
28:59 : there's there's more room for you to
29:01 : make mistakes like you forgot to update
29:05 : the parent link and now stuff is weird
29:08 : that kind of thing but uh so
29:13 : um so that is one way but um but let's
29:17 : say
29:18 : We're not gonna do it this way if we
29:20 : didn't have this parent link to go back
29:24 : uh how how would you do it
29:34 : that's
29:36 : that's uh
29:39 : that's sort of like how to get back up
29:45 : so method number one is
29:48 : maintain
29:51 : a parent
29:54 : point
29:56 : um
29:57 : that's actually two and three there's
30:00 : more ways to do this
30:03 : um yeah let's see if you can come up
30:05 : with one of two or three
30:11 : the idea that I had when I was saying
30:16 : create a tree on top of this
30:19 : or modify this all all of my ideas were
30:24 : sort of
30:26 : um
30:27 : centered around what we just talked
30:30 : about though was having having a
30:33 : each node having awareness of not only
30:36 : its children but it's parent so now that
30:39 : we've already sort of talked about that
30:40 : one now I'm I'm coming up short a little
30:42 : bit I'm kind of like okay okay what else
30:44 : can we do to be honest to be perfectly
30:47 : honest I'm still mulling it over okay so
30:51 : um
30:52 : okay so remember like last time
30:56 : I I gave you like an illustration like
30:59 : this where as we're moving down the tree
31:02 : it's like there's a window or a frame
31:05 : that follows you
31:08 : uh through the algorithm right yes and I
31:13 : said that well
31:15 : you know
31:18 : within every frame
31:21 : you're allowed to have
31:24 : these variables
31:26 : or like the variables that you choose
31:29 : like maybe
31:31 : maybe it when you're so current we have
31:34 : current
31:37 : um is Jenny
31:39 : maybe we you can also have previous
31:43 : in this case is not but when we're at
31:46 : the top so let me delete this to not
31:49 : confuse us so
31:51 : um
31:53 : we could if how do we so it's like yeah
31:56 : if we move down the tree
31:59 : then the current will become Jeff let's
32:02 : say
32:04 : and then previous will become Jenny
32:07 : um
32:08 : and then
32:11 : and then yeah so we remove it down here
32:15 : I guess down here we
32:18 : we change current to jam and previous to
32:21 : Jeff and when we realized the GM has no
32:24 : children
32:26 : uh we move the frame back up what is
32:29 : this mechanism of moving the frame back
32:32 : up
32:34 : um
32:36 : that depends
32:38 : um
32:39 : on
32:42 : I guess one way is just
32:45 : sort of
32:49 : um like uh if I were down here
32:53 : and the current was jam and previous is
32:57 : Jeff
32:58 : I want to move back up
33:00 : right maybe I just do
33:04 : current
33:05 : equals previous
33:09 : and then that will allow me to kind of
33:11 : move up
33:15 : um and and which means Jeff is here
33:20 : we've we've lost we still have the issue
33:22 : where we've lost our reference to jap's
33:24 : previous yeah we've lost Jenny we have
33:27 : no way to get back to Jenny Jenny so
33:30 : how can we get back to Jenny
33:35 : um
33:36 : that's that's the Deep philosophical
33:39 : question
33:41 : maybe it's
33:43 : it's building a
33:44 : tree that shows everything we've done
33:47 : that's that's
33:50 : like we we're at Jenny
33:53 : and then we before we move our pointer
33:57 : from Jenny to Jeff we create an entry in
34:00 : the new
34:02 : breadcrumb tree yeah yeah let's let's
34:05 : call yeah great red crumb
34:10 : let's have a variable called breadcrumb
34:13 : okay
34:15 : and basically
34:17 : uh breadcrumb initially so we're gonna
34:21 : add a new variable called breadcrumbs
34:23 : and breadcrumb is actually going to
34:25 : replace previous yeah we don't need that
34:29 : anymore yeah yeah so so we're using
34:32 : breadcrumb
34:33 : and so let's say we're at the beginning
34:38 : make some more room here all right
34:42 : oops my bread from all right
34:50 : breadcrumb initially is no and initially
34:54 : current is Jenny and we want to move
34:58 : down the frame to Jeff and basically
35:01 : we're gonna put Jenny in the breadcrumb
35:04 : and then we're gonna Set current to Jeff
35:07 : and then now the key is
35:10 : when we moved down to gem
35:16 : make uh the current Jam what what do we
35:20 : need to do to the breadcrumb we need to
35:23 : add Jeff to it but we need to model the
35:26 : relationship between jam Jeff and Jenny
35:30 : yeah
35:32 : so the key the key the key is ADD
35:36 : yes we add that we add Jeff without
35:39 : removing Jenny so breadcrumbs should
35:42 : actually be an array
35:44 : okay or a q of some sort or it could be
35:48 : a linked list actually yes yeah but like
35:52 : if you if you're doing like you know
35:55 : the high level language like JavaScript
35:58 : just use an array is totally fine
36:00 : so so we have a breadcrumb which is
36:03 : uh and the breadcrumb is basically this
36:07 : uh
36:09 : the path you took
36:11 : down
36:13 : down this tree thus far that's what the
36:16 : breadcrumb is so now you so now given
36:19 : that
36:20 : when you're down here and looking at jam
36:23 : and then you're done looking at Jam
36:25 : because Jam has no children you move
36:27 : back up
36:28 : you can just say you can just say okay I
36:31 : will set current back to Jeff and then
36:34 : I'm going to remove Jeff from the
36:36 : breadcrumb list and now we're back to
36:38 : Johnny and now we still have a reference
36:40 : to Jenny
36:41 : yes
36:43 : yep
36:44 : so that that is a very valid approach to
36:48 : doing this
36:49 : um and I I actually quite like this
36:52 : uh so yeah so we're gonna look at Jeff
36:55 : but but now we're back to Jeff
36:58 : we need to somehow remember
37:00 : that will have um
37:04 : we have already done the left side of
37:07 : the current node and now the next step
37:10 : is to do the right side of the current
37:12 : node right yeah true so so we somehow
37:16 : also need to remember that
37:18 : [Music]
37:18 : um
37:20 : how to remember it let me think
37:24 : we could stick more information into the
37:27 : breadcrumb possibly like
37:31 : um
37:39 : could we
37:41 : hmm
37:44 : instead of just storing well no that
37:47 : doesn't help because we've already
37:48 : deleted Jeff
37:50 : but I was gonna say instead of just
37:52 : storing
37:55 : the the reference like to Jenny or to
37:57 : Jeff inside the bread crumb could we
38:00 : store an object that's like
38:03 : the reference and also which children
38:06 : have already been traversed yep you
38:09 : could do this
38:13 : we can't delete Jeff when we get back up
38:15 : to Jeff we still have to have the entry
38:18 : for Jess
38:19 : there so we can say hey
38:22 : his Jeff's
38:24 : left child has already been traversed
38:30 : um
38:32 : there's there's an uh there's another
38:36 : way let me think
38:38 : so
38:45 : another way of storing these
38:48 : relationships hmm
38:52 : let me think I'm thinking another way is
38:56 : to
38:58 : uh like because when you're doing your
39:02 : left and then your right
39:05 : it's sort of like
39:08 : their jobs like I I need to do my left
39:12 : and then I need to do my right
39:15 : and I could potentially use a q
39:18 : to do like if I had a jobs array
39:24 : um
39:25 : and then
39:27 : Maybe
39:30 : maybe I can say like
39:33 : jobs dot push
39:37 : current
39:39 : uh jobs dot push and left
39:43 : jobs dot push current
39:47 : right
39:49 : and then just by doing
39:51 : pushing it to the job and then later on
39:53 : I'm gonna process
39:55 : the job
39:57 : and then
39:59 : to just by processing the job
40:02 : Halo again do this thing
40:06 : do do the pushing of the left and right
40:09 : onto the job queue again maybe
40:11 : okay that's another idea that that way
40:16 : this implicitly remembers the left and
40:19 : right for you whereas
40:22 : before you had to like remember oh did I
40:25 : do the left yet
40:27 : and now this may be sort of
40:31 : uh
40:32 : uh we flattened it into this
40:36 : linear job array
40:39 : um
40:40 : that's another idea
40:42 : so I have a question about that so the
40:44 : jobs I like this idea it makes sense to
40:47 : me but is are we basically saying for
40:51 : every node we're on like right now we're
40:53 : on Jeff
40:55 : try try to do
40:57 : the left job and the right job and then
41:00 : eventually we'll get down
41:03 : okay so let's say Okay so we're on Jeff
41:06 : and we do we go to run
41:09 : current dot left we get to jam
41:12 : we try to get do current dot left and
41:15 : current dot right for Jam but it's
41:16 : they're null so we know okay we're at
41:19 : the end
41:21 : but we're trying we're going to run that
41:24 : for every place we get to and then some
41:27 : of them are just going to be null and
41:28 : we're they're going to be unnecessary is
41:31 : that kind of it like we know every time
41:33 : we're checking for our left and our
41:34 : right
41:35 : every time we're checked yeah I mean we
41:38 : don't we may be able to check if it's no
41:40 : then we don't push it into the jobs
41:42 : that's fine
41:44 : um
41:46 : so
41:48 : um
41:51 : so we
41:53 : um let me think
41:55 : let me see if this
41:57 : works so like that like jobs is a job
42:01 : queue
42:02 : and then
42:04 : uh while
42:08 : uh
42:11 : uh the the idea of the queue is we're
42:15 : just gonna push
42:16 : uh we're gonna say like
42:19 : jobs dot push the root okay
42:25 : um so
42:27 : while
42:29 : jobs
42:31 : oh wow has jobs I'm gonna do pseudo
42:34 : Cooks uh well has jobs
42:38 : um I'm gonna do it like python sort of
42:42 : um we're gonna
42:44 : sort of uh
42:46 : DQ
42:48 : or pop
42:50 : equals jobs dot pop
42:53 : okay
42:55 : and then that just means like if we're
42:58 : talking about printing everything
43:00 : in the tree I'm just gonna print print
43:03 : the job
43:04 : uh value assuming job is just a note in
43:08 : the tree I'll print the jobs value
43:11 : and then I'm gonna uh jobs dot push my
43:18 : uh left
43:21 : I could do the track I guess or nulls
43:24 : but I could also
43:26 : drop that right but um well I could say
43:30 : here if
43:32 : um
43:34 : well yeah okay if
43:37 : If drop dot left
43:40 : then I will push it
43:45 : got that right then I will push it
43:51 : does this work
43:59 : um
44:04 : so okay let's see what that will look
44:06 : like so I have a
44:09 : so initially
44:13 : um here
44:16 : and then I push Jenny into jobs so jobs
44:20 : equals Journey
44:22 : and then I'm like
44:26 : and then allowed well uh uh there's jobs
44:30 : I'm gonna pop Jenny off and print Jenny
44:34 : okay
44:35 : so I maybe I have a log here that is the
44:39 : printed
44:40 : I printed Jenny and then now I'm gonna
44:43 : put Jenny's children onto this jobs
44:46 : array
44:48 : but are you out aren't you out of your
44:50 : condition while has jobs because right
44:52 : now there's no job
44:54 : I'm still here so I'm I'm I just did
45:00 : I just did that
45:03 : so the next operation is that so I'm not
45:07 : back to the has jobs condition actually
45:10 : I see okay yeah okay we're still in it
45:12 : we're still in the first iteration so so
45:14 : temporarily we're out of drops but we
45:17 : we're not done with this iteration of
45:19 : the loop so we could still have more to
45:21 : do uh and that's yeah it's hit kind of
45:24 : hinging on that so so now we're gonna
45:27 : basically push Jeff and John into the
45:30 : job queue with these statements here
45:39 : and then we get back here yeah we have
45:41 : jobs and then we're gonna pop John
45:45 : off and print done
45:47 : or maybe it's Jeff I don't know it
45:50 : depends on how the pop The Ordering of
45:54 : the pop doesn't matter too much right
45:56 : now
45:57 : um because I didn't ask for a specific
46:00 : order
46:02 : um and then here is Jeff uh so we
46:06 : printed Jeff and I we're gonna push Jeff
46:09 : through children
46:10 : into the job queue okay
46:15 : so
46:16 : that's going to be jam and Jefferson
46:22 : and then we do this again we still have
46:25 : jobs okay yeah we still have jobs and
46:27 : we're gonna take John off and print Tron
46:36 : so John is off
46:39 : and then we're gonna take John's
46:43 : children
46:44 : and add it to the queue so that John and
46:48 : Ken
46:49 : Kenny
46:51 : sure
46:52 : drum
46:54 : and Kenny go on to the queue
46:58 : and then we go back here and then we pop
47:00 : off the next job which is Jam
47:11 : and then we're gonna put gems children
47:13 : but Jam has no children so we skip these
47:16 : and we go back here
47:19 : and then uh probably gonna Grant
47:23 : Jefferson and take him off
47:30 : um and we're gonna put Jefferson's
47:33 : children but he has no children so the
47:36 : other of us have no children so we're
47:38 : just gonna keep going these three
47:41 : statements over and over again
47:43 : so so it just means we're gonna print
47:45 : John and Kenny at the end
47:48 : oh it works yeah yeah so this this works
47:53 : um I I like that's this method yeah so
47:57 : honestly I was um I wasn't sure until I
48:01 : just walk through it now but uh I've
48:04 : I've done this in the past but it's been
48:06 : a while but um so
48:10 : I mean this is good because it's a very
48:12 : small algorithm like we just wrote like
48:15 : eight lines or something or ten lines
48:18 : um
48:19 : and
48:21 : it can handle it
48:23 : um
48:25 : and
48:27 : um
48:29 : [Music]
48:30 : it
48:32 : I guess hmm
48:36 : the the difference between the like how
48:39 : does is this related to this breadcrumb
48:42 : idea that we came up with
48:45 : it's sort of like we're not tracking our
48:48 : breadcrumb necessarily
48:51 : it's more of
48:54 : um
48:56 : like like how do I answer the question
48:59 : you had of
49:01 : how do we get back to my parents how
49:04 : does this algorithm handle that
49:07 : so it handles it instead of a breadcrumb
49:11 : I wouldn't call it a breadcrumb it's
49:13 : it's using
49:16 : like
49:17 : every spot we are in the tree every node
49:21 : we end up landing on as we're moving
49:23 : down we're
49:25 : putting
49:27 : that node on the to-do list the jobs
49:30 : queue is like it's like a to-do list
49:32 : it's like
49:34 : we're adding it to the this still needs
49:36 : to be processed which is the whole would
49:38 : be the whole point
49:40 : so so it's it's actually it's not that
49:43 : we're going back up the tree it's just
49:46 : that as we're going down with
49:53 : everything we need to do yeah uh
49:57 : uh beginning at the top in into these uh
50:01 : yeah these to do items
50:03 : which will later get processed so we're
50:06 : not worried about losing them because we
50:09 : know it'll later be processed exactly
50:13 : yeah it's it's really good I I'm
50:16 : I like this the more I think about it
50:19 : the more I'm I'm just like yes this
50:21 : makes sense to me good I I feel like
50:24 : maybe there's a downside to this like
50:26 : there almost always is some negative but
50:28 : right now I'm I'm still like I don't I
50:31 : don't even see the downside to this I I
50:33 : guess we haven't really analyzed the
50:35 : performance of it but it's
50:38 : okay what is the Big O of this
50:41 : algorithm
50:45 : relative to the number of elements that
50:49 : are index free
50:53 : yeah I think it okay so it's
50:57 : the number of jobs that gets pushed is
50:59 : going to be the number of elements in
51:01 : the tree
51:02 : yeah and that's the number of things so
51:04 : I do it is it in yeah yeah so it's not
51:08 : incredibly performant yeah
51:11 : can you do better than n
51:18 : um I know it can be done right now I'm
51:21 : like okay how
51:23 : how
51:24 : um
51:27 : but why do you know it can be done
51:31 : well okay I guess I should say I I'm not
51:33 : saying it can be done using this method
51:36 : but I guess I just have confidence that
51:38 : someone has come up with methods out
51:40 : there that are better than him
51:42 : because those Computer Science Guy
51:44 : they're pretty smart exactly and this is
51:47 : a pretty you know common thing that has
51:49 : to be done I'm just sure somebody has
51:51 : come up with a more performant way to do
51:54 : it okay but maybe it's not this way I
51:57 : mean this way I think I like it so much
52:00 : because it's just it's very tidy and it
52:02 : just sort of makes sense it's very
52:03 : intuitive
52:05 : um but yeah they go off and it's not
52:06 : very good so they go well okay I would
52:10 : actually argue that
52:12 : uh
52:14 : in this case
52:15 : you cannot do better than bigger event
52:18 : and
52:20 : the reason is
52:22 : is if you think about it is kind of
52:25 : intuitive because
52:27 : I asked you to print every element in
52:30 : the tree
52:32 : and which by definition means if if
52:37 : there were 10 elements in the tree well
52:39 : you have to print 10 things if I double
52:42 : that
52:43 : you would have to print funny things if
52:47 : I uh triple that you would have to print
52:50 : three times as many things
52:52 : so it's inherently touching having to
52:55 : touch every yeah
52:57 : yeah I see that point I see that point I
53:00 : do yeah so so in this case uh and Big O
53:04 : event is the best you can do and and
53:06 : there's actually no way you can improve
53:09 : on that because if you improved on that
53:11 : it means you're not touching everything
53:13 : in the tree
53:15 : um okay so so this is good
53:19 : um this is good
53:20 : um
53:23 : no
53:27 : I don't know
53:30 : let me think
53:32 : now okay so now that we've solved this
53:35 : problem number one
53:37 : how much time do we have
53:40 : not very much oh not very much okay yeah
53:44 : okay
53:46 : um maybe I'll just
53:50 : resolve the problem number one which is
53:53 : print every element in the tree uh so
53:56 : problem number two is
54:01 : uh print everything element in the tree
54:04 : in order
54:08 : every element
54:10 : in the tree in order
54:14 : um
54:16 : so which which is that uh animation we
54:21 : did which I want I want to go this this
54:24 : direction
54:26 : so maybe maybe we'll just stop there and
54:31 : uh and uh
54:32 : we'll re reflect on it how that might be
54:36 : done and we'll talk about it next time
54:38 : all right the Cliffhanger for next
54:40 : week's episode