# Binary Tree Traversal: Part 1

Published on May 28th 2023Duration: 54:43Watch on YouTube

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