Binary Tree Traversal: Part 2 (with Recursion)

In this episode, Carol and I discover recursive traversal of binary search trees: in-order, pre-order, and post-order.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : well I made a copy of this and then and
00:04 : then like you you're calling into this
00:07 : guy at some point in the parent you made
00:09 : another call
00:11 : and then it sort of expanded to the next
00:15 : level and then the next level gonna
00:18 : expand again
00:19 : to that and then it's it's like
00:22 : something inside of that frame has
00:26 : expanded to the next one
00:28 : it's like that okay that's a good
00:32 : visual I like that
00:38 : um all right so last time we talked
00:40 : about how to Traverse all the notes in
00:42 : the tree and we came up with this job
00:45 : queue
00:47 : aka the to-do list approach
00:51 : um and
00:54 : and then today and then I guess the next
00:59 : challenge was
01:02 : how do we print every element in the
01:05 : tree in order
01:07 : but before we get into that I'll just uh
01:11 : confess that
01:13 : this drop Cube based way of doing it is
01:17 : not the most common way
01:21 : uh yeah it's actually like if you if you
01:23 : Google for
01:25 : how to Traverse a binary tree you will
01:28 : not find it'll be harder to find this
01:31 : way
01:32 : yes so
01:35 : um
01:36 : that's not to say it's not a good way
01:38 : but um I I like this way myself
01:42 : um but um
01:44 : I think it's not as well suited for the
01:49 : Second Challenge
01:51 : which is to print everything in order
01:55 : so before we talk about
01:59 : how to do number two
02:01 : I want to also show you how to do it the
02:05 : more common way
02:08 : um
02:09 : without the Dropkick thing
02:12 : um and that way you actually alluded to
02:16 : it last time which is you said you said
02:20 : something like
02:23 : um it's almost like
02:25 : I need another tree structure
02:29 : while traversing it that maps onto this
02:32 : tree structure
02:34 : yeah
02:35 : and
02:38 : and that actually matches how things are
02:42 : done
02:44 : um
02:46 : in in the second way so what's this
02:49 : what's this what's the second way
02:52 : um
02:53 : if I say the word recursion
02:57 : does that ring a bell yes
03:00 : okay so can you imagine a recursive
03:05 : function that can Traverse every element
03:09 : in this tree
03:15 : yeah so let's think so I'm gonna write
03:19 : yeah recursive
03:22 : traversal
03:25 : um I'll get recursive tree traversal
03:28 : so that's our method number two for
03:31 : traversing a tree like what will that
03:33 : look like
03:35 : and
03:37 : um I don't know if you want to uh I'll
03:40 : just let you think yeah okay
03:43 : so I'll I'll try to think out loud here
03:45 : so we can dialogue
03:48 : um so we're going to start I would
03:51 : assume I think it's pretty good
03:53 : assumption we're going to start at the
03:54 : root
03:55 : of the tree and then we're going to
03:59 : perform some series of actions that can
04:03 : be
04:05 : call so it's going to be there's going
04:07 : to be a condition at which we know to
04:09 : break out of the recursion we have to
04:11 : set that condition
04:14 : we'll call it determinating condition
04:19 : okay and we'll figure out what that is
04:21 : and I think that might be
04:24 : um a node with two null children but but
04:27 : no that can't be right because we can
04:29 : get to the bottom and then we still have
04:31 : to okay never mind scratch that so I'm
04:33 : going to keep going with with the high
04:35 : level okay so we have to figure out our
04:37 : terminating conditions
04:38 : and then
04:40 : we want to
04:43 : determine what series of steps break the
04:48 : series of steps but we have to take into
04:53 : like the smallest repeating sequence
04:56 : that can be be called again on the sub
05:00 : tree until the terminating conditions
05:02 : met so we want like okay so we want
05:06 : I think we want to make
05:09 : we're gonna have to store some things
05:11 : and I I don't know exactly what all
05:14 : we're gonna have to store probably
05:17 : well I'm initially thinking might be
05:19 : Overkill but we're I think we're gonna
05:21 : have to store
05:23 : with our current node
05:27 : and
05:32 : are
05:38 : so we're still trying to print we're
05:39 : trying to print every element but in
05:41 : order
05:42 : so basically like that graphic that
05:45 : visual that we've done where we're
05:46 : moving the line from left to right
05:51 : Well for now for now don't worry about
05:54 : the in order aspect just yet okay just
05:58 : get to every node in the tree and then
06:01 : we'll deal with that later
06:03 : gotcha okay
06:04 : okay so right now we're just getting to
06:06 : holidays we're printing every element
06:07 : okay
06:10 : so
06:16 : question I'm now grappling with is
06:20 : do we
06:22 : go completely down one side of the tree
06:24 : and then back up or do we work our way
06:27 : down both sides simultaneously
06:31 : but how would we work our way down both
06:33 : sides simultaneously that's kind of what
06:36 : we did in the method last week where we
06:39 : pushed them
06:42 : we're not doing it simultaneously but
06:46 : it's not like we're starting
06:49 : two processes in parallel okay we're
06:53 : still doing things in a specific order
06:58 : um and I guess when we did when we did
07:00 : the Q
07:02 : method
07:04 : the order in which the names are printed
07:07 : that's the order in which we reach all
07:10 : the nodes right kind of kind of yes yeah
07:14 : like Jenny Jeff John and then so it's
07:17 : like we did level one and then we did
07:19 : level two and then we did all the ones
07:21 : in level three
07:23 : yeah
07:25 : um that's fine like if if we can get the
07:28 : recursive traversal to do that that's
07:31 : fine
07:32 : or or not or I just care about getting
07:35 : to every note for now okay
07:39 : so
07:43 : it's the parent node so we need to know
07:46 : what our current node is and what its
07:48 : parent wise I think so so like like
07:52 : variables
07:54 : Kern
07:55 : and parent let's say
07:58 : yeah and then also
08:02 : we're gonna need to know so uh also like
08:05 : I'm gonna write out what calling this
08:09 : function might look like maybe we'll
08:12 : call it Traverse
08:19 : Trend or something and then we pass it
08:21 : the root node so maybe
08:24 : Traverse print takes a note of some sort
08:29 : and because it's a recursive function at
08:32 : some point it'll call itself exactly
08:36 : okay so it's going to take in the parent
08:39 : node
08:43 : oh so we said good and the parent as
08:47 : well so we might pass that in as a
08:50 : parameter so initially
08:52 : or passion no that's the parent let's
08:55 : see okay I like that that makes sense
08:58 : okay so initially
09:01 : we have Traverse print with passing in
09:04 : Jenny and null
09:06 : and then I think the next thing would be
09:10 : to print that value
09:12 : print the current value okay just go
09:14 : ahead and print it okay yeah
09:17 : print node then
09:22 : let me move I'll move
09:25 : so we move our pointer to
09:31 : one of our children
09:33 : oh move our pointer to oh oh I see what
09:38 : you're saying like start traversing the
09:40 : tree let me move this stuff uh let me
09:43 : try moving this
09:46 : is it shift yes it's shift
10:00 : okay
10:09 : um so when you say move the pointer so I
10:13 : guess like
10:14 : this Frame thing I think it's important
10:17 : again because this Frame thing is very
10:21 : well matched to what recursion does
10:24 : uh because
10:26 : when you're calling a function actually
10:28 : in fact
10:31 : um
10:34 : there is a frame
10:36 : uh so curling this of like this so like
10:41 : when you make a function call uh we
10:44 : actually add a news thing called the
10:47 : frame
10:48 : on the programming stack
10:51 : and that frame is responsible for
10:54 : storing all the local variables inside
10:57 : your function
10:59 : so which means like if we if we say this
11:02 : is a
11:03 : rectangle is a representation of a frame
11:08 : then we're saying hey inside this Frame
11:12 : uh we're gonna store the variables
11:15 : uh
11:17 : and the current is going to be Jenny
11:22 : and then we're gonna have a parent
11:26 : which is
11:29 : um no
11:31 : uh so like something like that oh yeah
11:35 : uh I probably shouldn't have done that I
11:38 : can imagine them being there
11:41 : okay so something like this and then uh
11:46 : and we talked about moving the frame
11:48 : down the tree
11:52 : um
11:55 : well that's a valid way of looking at it
11:59 : um in reality
12:02 : uh when you move the frame down the tree
12:05 : it's the parent frame has made up
12:09 : made a inner
12:13 : function call
12:15 : right
12:16 : and when you make the when you make it
12:19 : so that would happen when you um how do
12:22 : we get rid of these boxes by the way
12:27 : okay maybe that's maybe that's it okay
12:30 : so ah okay
12:33 : go away boxes all right so at some point
12:36 : in your function you're going to see
12:38 : something like hey Traverse current note
12:42 : that left right
12:45 : um and this is a recursive call which
12:49 : means and but when you call this
12:52 : function
12:53 : the parent frame doesn't go away
12:56 : right right
12:59 : you still remember everything in the
13:01 : parent frame
13:03 : you just increased a you you call this
13:06 : function sort of like nested inside the
13:10 : parent frame
13:12 : so
13:13 : um
13:15 : so I guess that so you should keep that
13:19 : in mind like when you move it it's more
13:22 : like
13:23 : well I made a copy of this and then and
13:27 : then like you you're calling into this
13:30 : guy
13:32 : uh but this is like a
13:37 : like you opened it up from
13:40 : from the parent like is at some point in
13:44 : the parent you made another call
13:46 : and then it sort of expanded to the next
13:50 : level and then the next level gonna
13:53 : expand again
13:54 : to that and then it's it's like
13:57 : something inside of that frame has
14:01 : expanded to the next one
14:03 : just like that okay that's a good
14:07 : visual I like that
14:10 : um so I think that it seems particularly
14:13 : relevant here and what we're trying to
14:16 : do because we haven't lost
14:20 : well we still have the first value of
14:23 : current and parent preserved and then we
14:26 : get the next value of current parent
14:29 : yeah exactly so we can fill these guys
14:32 : out so in inside the nested frame the
14:37 : current is going to be pointing to Jeff
14:40 : but the parent actually has a value now
14:44 : yeah the parent is actually pointing to
14:47 : uh Jenny
14:49 : enough like that and then in here
14:53 : current is uh pointed to jam
14:58 : and then uh
15:00 : and then whoops
15:04 : Aaron
15:05 : is going to uh be pointing to Jeff in
15:09 : that frame
15:11 : um and this will happen sequentially so
15:14 : it's not like they're all
15:16 : here
15:18 : at the same time it will more be like
15:21 : when you're executing in the frame of
15:24 : Journey
15:25 : then when they get to a certain point
15:27 : pop a new frame for Jeff and then when
15:31 : Jeff gets to a certain point pop comes a
15:34 : new frame for jam and then Jam is going
15:38 : to finish its operations and then Jam's
15:41 : frame will get destroyed and we come
15:44 : back to Jeff and Jeff will need to do
15:47 : the rest of its thing and then you will
15:50 : need to pop a new frame for Jefferson
15:53 : and so forth and then when Jefferson is
15:55 : done it pops back into just and when
15:58 : Jeff is done it pops back to Jenny and
16:01 : it'll be like sequentially like that
16:03 : it's not like everything at once
16:06 : um
16:07 : yeah
16:09 : cool so I I think
16:13 : then it it drawing it out and and like
16:17 : talking through like that really is
16:19 : helpful to kind of thinking through what
16:21 : we need to do here so it's it's like we
16:24 : need to
16:28 : check to see
16:30 : if I can't remember what we called it
16:33 : um node like left let's say if node left
16:37 : has value okay yeah so if I don't know
16:42 : dot left is not no let's say sure then
16:48 : we want to
16:50 : call
16:52 : Traverse print
16:54 : with node left
16:57 : right
16:59 : and then
17:01 : if
17:02 : we want to keep doing that we want to
17:04 : keep until we get
17:06 : to a node left that is null
17:09 : so here is where your uh normal
17:15 : your like normal
17:17 : uh sort of loop
17:20 : based programming
17:22 : mindset uh needs to kind of be
17:27 : challenged that kind of thinking
17:30 : so
17:32 : that that iteration doesn't need to
17:35 : happen in this code
17:37 : and the reason is I hope I misspelled
17:40 : Trooper the reason is when you call
17:43 : Traverse print
17:46 : this call Will already take care of
17:49 : traversal for all the children
17:53 : of the sub note dot left
18:01 : okay recursion is this weird thing when
18:06 : you yeah when you're uh like initially
18:10 : getting practice with recursion
18:14 : the way
18:15 : I feel that the way I uh
18:20 : uh had to
18:23 : to tell myself like the thing I had to
18:26 : tell myself is when I make a recursive
18:29 : call
18:30 : I just have to trust it on faith
18:34 : that this will do
18:36 : uh
18:38 : everything that is supposed to do
18:40 : correctly oh I forgot to put in a parent
18:43 : and and uh
18:46 : if it did everything is supposed to do
18:48 : correctly
18:50 : means this will actually correctly
18:54 : recursively print
18:57 : all the elements
18:59 : including the descendant of my left node
19:07 : okay which means there's no need for me
19:10 : to Loop
19:16 : because because by the same logic all I
19:19 : have to do is call Traverse print on the
19:22 : root of my tree and I would expect it to
19:25 : print every element in in that tree
19:27 : right
19:28 : so by this by the same logic if I just
19:31 : call Traverse print on my left child I
19:34 : would expect my left child and all its
19:37 : descendants to be printed
19:40 : which which is why I only have to call
19:43 : this without additional iteration or
19:47 : looping
19:49 : so the two lines of code or the three
19:52 : that we have now the print line one
19:55 : print node value and then we're doing
19:58 : the check to see if our left node is not
20:01 : null then we then we call recursively
20:04 : like that's really all we need to get
20:07 : down the but we still have to handle the
20:09 : right side
20:10 : you still have to handle the right side
20:12 : correct but like that those three lines
20:16 : the recursive the way the recursive
20:19 : call works that will take us all the way
20:21 : down the left side
20:23 : yeah yeah because so let's just imagine
20:28 : what happens
20:30 : um
20:31 : so
20:32 : Who start with nothing again
20:40 : [Music]
20:46 : okay so we we start at here
20:50 : and then uh we say hey print note that
20:55 : value
20:56 : so what we end up doing is
21:01 : so you're gonna print Jenny
21:03 : and then we're gonna if note that left
21:06 : is exist
21:08 : I'm gonna say it exists
21:10 : uh if not that left exists then we're
21:14 : gonna do this call this recursive call
21:18 : at least it probably come up with a
21:20 : parent
21:22 : for that parameter
21:26 : um
21:28 : this this would just be node right it's
21:31 : the parent of left.net note dot left
21:36 : um so we'll
21:38 : recursively call Traverse print and then
21:42 : and then we're back at the top but it's
21:45 : at the nested level and then and then
21:48 : line one is just print that value so
21:51 : we're gonna print Jeff right yep
21:55 : um
21:57 : we're gonna print just and then the GIF
22:00 : frame again we're gonna say if node.lef
22:03 : exists
22:04 : and then print Traverse print
22:07 : load that left and that's gonna get us
22:09 : to jam
22:14 : you don't have to keep drawing the
22:16 : squares unless you just want to I do
22:18 : feel like I have it
22:20 : okay
22:22 : um so yeah so we're gonna do that we're
22:25 : gonna print jam and then here
22:30 : Jam doesn't have a left so we're not
22:33 : gonna do this anymore
22:35 : and then uh
22:38 : and then we can actually finish this
22:40 : Frame because we reach the end of the
22:43 : function for Jam
22:48 : so then it goes back to where it is yeah
22:51 : we pop back to just frame and just frame
22:55 : was sort of suspended in here waiting
22:58 : for gems frame to finish so it would be
23:01 : like we completed the function call to
23:03 : Traverse print for Jam
23:06 : and then after that there's no more
23:08 : statements so we also complete the frame
23:10 : for Jeff
23:12 : and then again we're back to Jenny's
23:14 : frame and then again at Jenny's streamer
23:17 : we also suspended on this line
23:19 : and then now we come back from this line
23:22 : and then Jenny's frame is also completed
23:25 : because we reached the end of her frame
23:28 : so we destroy all the frames and then
23:31 : we're gonna return
23:33 : um return back to the
23:36 : original calling line which is this
23:40 : um and we end up just printing three
23:43 : names
23:45 : um but you know we haven't done the
23:47 : right side
23:49 : right
23:52 : so so let's complete the right side yeah
23:54 : the right side yeah so I I
23:59 : I want to say
24:00 : that when we
24:03 : exited out of the frame for Jam and then
24:07 : we were back
24:09 : in the suspended Jeff frame that we we
24:12 : want to have some logic in there that
24:14 : says like an else if maybe
24:17 : that says
24:20 : um
24:22 : else if node right
24:25 : and then call Traverse print again with
24:29 : node right
24:31 : it should have been else if though
24:33 : because like you're assuming it either
24:36 : has a left or a right
24:38 : if if you do an else if
24:41 : right
24:43 : and is that
24:45 : is it not safe to assume it has a left
24:48 : or a right
24:49 : well and I have
24:51 : yeah it might have both
24:54 : yeah so maybe it's just a second if yeah
24:57 : it's just a sickness yeah okay
25:01 : so we want to say if node right exists
25:06 : and then call Traverse print with node
25:09 : right and node as the parent
25:12 : uh-huh
25:13 : yeah exactly so
25:16 : um so if we do this
25:19 : then after jams frame so it should Jam
25:23 : we're gonna fast forward they're the
25:26 : same so like uh if we're at jams frame
25:31 : um we're gonna print Jam
25:33 : and then I guess just take my word for
25:36 : it that everything that happens so far
25:39 : is the same yeah yeah so yeah uh and
25:43 : then
25:44 : um
25:45 : you're gonna see that jam doesn't have
25:47 : the left note so it skips this and it
25:50 : also doesn't have the right no so it
25:53 : skips this one as well so we're gonna be
25:56 : done with jams frame
25:58 : and come back to Jeff and now Jeff was
26:02 : suspended in this line and now it's been
26:05 : returned to Jeff
26:07 : so Jeff is going to continue on this
26:10 : line
26:10 : and see that oh I do have a right side
26:13 : so now it's gonna instantiate a new
26:16 : frame
26:17 : for uh Jefferson
26:20 : and then Jefferson is gonna print itself
26:27 : um and then Jefferson is gonna see it
26:29 : has no children so it's gonna be done
26:32 : very quickly and then and then Jeff is
26:35 : gonna
26:36 : it's returning to Jeff after this call
26:39 : and then Jeff is gonna be done after
26:41 : that so it's just it's gonna pop off
26:45 : and then we're back to Jenny's frame and
26:47 : Jenny was actually suspended here so so
26:50 : when you're if you're doing this kind of
26:52 : stuff by hand
26:54 : uh which I do make my students do
26:57 : sometimes
26:58 : like yeah be the computer right because
27:02 : otherwise you have to know how the
27:04 : computer is going to behave precisely
27:08 : like you should be able to replicate it
27:10 : yourself using pencil and paper
27:13 : um but if you were to do that you
27:16 : actually have to keep track of like what
27:20 : line
27:21 : was Jenny's frame suspended on when it
27:26 : created the Jeff frame because after
27:28 : Jeff is done you have to know
27:31 : what line to sort of restart from In the
27:35 : Journey from so I I would like
27:37 : like usually I would do a little arrow
27:42 : here
27:44 : um in the journey frame
27:47 : or write down the line number
27:49 : yeah for for the journey frame if I if I
27:52 : if I draw the frames as
27:55 : so like as I draw like oh this one frame
27:59 : this is Jenny and then another frame
28:03 : this is Jeff and I'll write like the
28:05 : line number like
28:07 : we we call uh
28:12 : called from line
28:16 : line five or something that's how we
28:19 : opened up this Frame so when we when
28:21 : this Frame is destroyed we know to go
28:25 : back to line five which might be this
28:27 : line and then and then in the journey
28:29 : frame we start from line five again
28:32 : that makes sense
28:34 : um
28:35 : yeah so anyway we're back on this line
28:39 : in the journey frame and we're just done
28:41 : with this function and then I'll
28:42 : continue and then we're gonna have to go
28:45 : on to Jenny's right side yes
28:48 : so it'll be it'll be like that and then
28:52 : we'll get to print John here
28:56 : etc etc and uh oh I won't belabor it but
29:00 : everything will be similar on that side
29:05 : uh and that's how we Traverse this tree
29:07 : yeah
29:09 : um
29:10 : let me think
29:11 : one thing
29:13 : oh there's a couple of things that we
29:15 : can simplify with this code okay uh one
29:18 : is we actually never made use of the
29:21 : parent variable it's not necessary we
29:24 : don't really need it yeah yeah we
29:25 : actually don't need it so there's no
29:27 : need to maintain in this case that there
29:30 : are some cases where you might need it
29:33 : but this case we don't and another thing
29:36 : is
29:37 : um so we also can get rid of it here
29:39 : another thing is you actually could move
29:43 : this null check
29:45 : to the top
29:46 : instead of having two Now tracks here I
29:50 : could say
29:51 : if node
29:53 : exist
29:56 : or if if the if
29:59 : uh note does not exist
30:03 : uh we're gonna do an early return
30:08 : and then that way you don't actually
30:10 : have to do these two checks so what
30:12 : would happen and this at
30:15 : this is usually like this way usually
30:19 : yields more condensed code because you
30:22 : have just one check and this is the
30:25 : terminating condition by the way okay so
30:27 : so you you just have one terminating
30:31 : condition check instead of have two
30:33 : separate ones
30:34 : lying somewhere in the code and it's a
30:37 : little bit more easy to think about or
30:40 : maintain later on
30:42 : um so so this does mean that you're
30:45 : gonna have end up with like you create a
30:47 : frame
30:48 : but jam and jam is like just Traverse to
30:52 : my left and it's left is nothing
30:54 : and you you'll have a frame for the case
30:56 : of nothing and then at the beginning of
30:59 : this Frame it'll just say oh it's
31:01 : nothing so I'm just gonna return and I
31:03 : destroy the frame right away
31:05 : okay yeah that makes sense it kind of
31:08 : seems like it's more work it's actually
31:10 : more work for the computer
31:12 : because uh this bit is less work for the
31:16 : human because there's less code to read
31:18 : here but for the computer it has to make
31:21 : this extra frame which is actually
31:24 : somewhat expensive
31:27 : so why wouldn't we if that's the case
31:29 : why wouldn't we
31:30 : have
31:32 : a couple more lines of code
31:34 : to optimize
31:37 : um
31:38 : just because
31:40 : this code just looks more condensed and
31:44 : it seems like
31:47 : hmm
31:49 : well okay like
31:52 : optimization is that there's different
31:56 : schools of thought surrounding
31:58 : optimization like making sure your code
32:01 : is as fast as it can be
32:04 : um
32:06 : and
32:11 : um this so so they are programming
32:16 : language
32:18 : that can actually automatically optimize
32:21 : this is one thing okay uh so that it
32:25 : will be fast anyway but that's not
32:28 : that's not guaranteed like I don't I
32:30 : don't know if
32:33 : it's not guaranteed that that statement
32:36 : so
32:37 : uh you might have to verify and I don't
32:40 : know if it works in JavaScript or not I
32:42 : have a feeling no
32:44 : although it's hard to say because the
32:47 : JavaScript compilers are super fancy and
32:50 : they're getting better all the time
32:52 : um but another thing is there's a school
32:55 : of thought that you shouldn't
32:59 : worry about optimizing your code for
33:02 : performance
33:03 : at the outset
33:07 : um
33:08 : because other concerns are also
33:12 : important like code readability
33:14 : sure so when when you have a need to
33:19 : optimize for that there's a famous
33:21 : saying code like premature optimization
33:24 : is the root of all evil
33:27 : which is a uh perhaps
33:32 : a little strong
33:34 : sure rude volleyball yeah it's slightly
33:38 : strong and I I think overly strong but
33:42 : like with I think with any kind of
33:45 : debate where
33:49 : there's there are good points that can
33:52 : be made on both sides uh both sides try
33:57 : to sort of uh fight really hard
34:01 : uh to win the argument and I think this
34:05 : quote is just an example of that so so I
34:08 : think both sides has uh has a good point
34:11 : and I'm not gonna take either side in
34:14 : this case
34:17 : um but that I do for teaching I do like
34:19 : just having very condensed cook okay
34:22 : sure
34:24 : um all right so
34:31 : um okay so now
34:32 : maybe we can finally get to
34:35 : the ordering problem so how do we uh so
34:39 : here have we printed things in order no
34:42 : no we should print Jam first and then
34:47 : Jeff
34:48 : and then uh Jefferson and then Jenny so
34:52 : that's the output that we want
34:54 : so
34:56 : can you think of a way to like just look
34:59 : at this code it's so nice
35:01 : uh there's only like five lines of code
35:04 : in this video it's not like our previous
35:07 : function was nice too
35:09 : it's not bad there's like 10 lines of
35:12 : code here uh but now it's just five
35:15 : lines
35:17 : um so like
35:19 : how would you change these five lines
35:24 : to get this tree to print in order
35:28 : okay so if I'm when you say change these
35:32 : five lines do you mean I'm not adding
35:34 : anything else
35:36 : uh
35:40 : um I'm not gonna
35:42 : I'm not gonna put words in your mouth
35:46 : okay so here let me let me say it this
35:48 : way so my my first thought
35:53 : after we've written this Traverse
35:55 : cursive function my first thought is
35:57 : well I think we have to
36:01 : start from the top and work our way down
36:03 : like that's just how traversing
36:06 : she works so my thought is
36:10 : instead of just immediately printing
36:13 : the names or the values there might not
36:16 : be names the values why don't we
36:19 : organize them why don't we sort them and
36:22 : then in the end print the sorted list
36:24 : but I also think I might be taking the
36:27 : wrong approach like sure we could do
36:30 : that but maybe there's a better way to
36:32 : do it so yeah
36:35 : there's a simpler way there's a simpler
36:37 : way okay so I want to sort of table that
36:39 : thought for a minute and just kind of
36:41 : look at these lines of code and see
36:44 : um node left node right so we're
36:46 : printing the value
36:49 : so we're each iteration through each
36:51 : time we call this we're printing if the
36:54 : value exists we're printing it and then
36:57 : we're calling
37:00 : the function recursively first on node
37:02 : left and then on node right
37:08 : maybe we don't print first
37:12 : let's see if we didn't print first if if
37:15 : we first
37:19 : we because we want to start all the way
37:21 : down at the bottom we want to
37:23 : we want to Traverse all the way to our
37:26 : bottom and then start printing yeah
37:28 : that's what we want to do
37:31 : so I think we want to move our print
37:34 : statement in between our two calls yeah
37:38 : so so just dude so uh maybe I'll make a
37:42 : new copy of this sure
37:45 : uh and and I'm not like fully convinced
37:47 : that I've that I've got this but I'm
37:49 : just kind of thinking out loud here to
37:51 : be honest
37:52 : no that's the best way to do it uh tree
37:56 : Traverse so I'm gonna call this uh in
38:00 : order
38:02 : uh this is actually what it's called in
38:05 : the literature
38:08 : so creative yes
38:12 : um okay I'm gonna so perhaps I will name
38:18 : this
38:19 : in order
38:21 : as well
38:27 : oh by the way
38:29 : the name for the first one
38:33 : is called
38:35 : pre-order
38:39 : which sounds like you're trying to buy
38:42 : some very popular item but uh but that's
38:48 : not what it means uh it's it's it means
38:51 : you're gonna print
38:53 : um you're gonna print yourself first
38:56 : before traversing your children that's
38:59 : what pre-order means ah okay
39:03 : um and then uh now we're gonna do in
39:06 : order and you're saying uh why don't we
39:08 : just move this print statement in
39:10 : between
39:12 : uh these two
39:15 : recursive calls so let's see what will
39:18 : happen happens yeah if we did that
39:22 : um so
39:23 : I'll just zoom out a little bit I guess
39:26 : all right so initially we would be
39:30 : looking at Jenny yeah and then I'm gonna
39:33 : okay and then we're gonna well it does
39:38 : exist so continue
39:40 : um so we're gonna make a new frame for
39:43 : Jeff and then
39:46 : um
39:47 : and then Jeff does exist so we continue
39:50 : and then we're going to make a new frame
39:52 : for Jam yep
39:54 : and then Jam does exist and we're gonna
39:58 : make a new frame regardless for each its
40:02 : left child which is nothing yep and then
40:04 : we're in this Frame and the note does
40:07 : not exist so we're gonna be done with
40:09 : that frame and then we're back to jam
40:12 : and now when we're back yeah exactly
40:14 : we're on this line
40:16 : we've done with this line and then now
40:19 : we're gonna print Jam
40:22 : yep
40:24 : and then now it's gonna we're done with
40:27 : the print statement and then we're going
40:28 : to Traverse to the right of jam
40:31 : uh over here that's nothing so we're
40:34 : gonna exit that frame right away and
40:37 : then now we return to this line in the
40:40 : jam stream and then we're gonna be done
40:43 : with jam and then we're gonna go back to
40:45 : Jeff and then Jeff was uh suspended on
40:49 : this line so now we're done with this
40:51 : line
40:52 : and then we're going to print Jeff
40:56 : and after that we're gonna Traverse to
40:59 : the right of Jeff yeah and now we're and
41:03 : then now we're in Jefferson Jefferson
41:04 : does exist we're gonna go to the left of
41:08 : Jefferson but then that frame gonna go
41:11 : away right away and then now we're gonna
41:13 : print Jefferson
41:16 : and then now we're gonna do another
41:18 : frame for the right of Jefferson and
41:20 : then that frame goes away and then
41:23 : Jefferson is done that frame goes away
41:25 : and we're back to Jeff and it was on
41:28 : this line and it's done now so Jeff is
41:32 : done as well
41:33 : wait get rid of Jeff stream and we're
41:36 : back to Jenny uh Jenny was uh suspended
41:40 : on this line to do just
41:43 : and then now we actually get to print
41:45 : Jenny yeah
41:47 : and then now we're gonna go to the right
41:50 : side of Johnny
41:52 : and then yeah John John exists so we
41:56 : keep going and then we're gonna jump
41:58 : John exist and then we're gonna do the
42:01 : left side of drone there's nothing there
42:04 : and then we're gonna print drone
42:09 : and then after printing drone we're
42:11 : gonna go to the edge right side there's
42:13 : nothing there and then now we're back to
42:16 : John
42:18 : and then John is done
42:20 : come back to John and John was on this
42:25 : line on it doing its left side
42:27 : and then it's done with that and now
42:30 : we're gonna print John
42:32 : and then and then now we're gonna do the
42:35 : right side of John
42:38 : uh which is Kenny Kenny exists we're
42:41 : gonna go to the left side but there's
42:43 : nothing there so we're just gonna make
42:45 : the frame really quickly and delete it
42:47 : and then uh we're over here we're gonna
42:51 : print uh Kenny
42:54 : and then again we're just gonna do that
42:57 : go to the right side of Kenny there's
43:00 : nothing there and we're done with Kenny
43:02 : uh we come back to John's frame on this
43:05 : line and then after that he's done and
43:08 : then come back to Jenny's frame on the
43:10 : last line and then Jenny is also done
43:13 : and we're finished
43:15 : so cool
43:16 : yeah just that one tiny little change
43:18 : it's very elegant this whole thing of
43:21 : the tree and everything being in order
43:23 : from left to right
43:25 : blows my mind I want to know what the
43:27 : inspiration do we see this pattern in
43:29 : nature I don't know like where did
43:31 : someone come up with this
43:34 : we do see this pattern in nature look at
43:37 : how many not well not only just the not
43:41 : only the actual trees that you see in
43:44 : nature
43:46 : um but that's definitely true
43:49 : like if you if you see look at the
43:52 : leaves of some trees
43:55 : you see that there are smaller patterns
43:58 : in the leaf that are sort of smaller
44:02 : versions of the whole Leaf itself yeah
44:05 : so those are called fractals where yeah
44:08 : yeah that's what I was thinking of like
44:10 : the the cauliflower for example is a
44:14 : classic fractal where this it's sort of
44:17 : like they're smaller and smaller
44:18 : versions of itself uh uh fractals are
44:23 : fascinating too
44:25 : um I could I could do that but that's
44:29 : not for now they're not fair enough
44:32 : yeah uh yeah fractals are super amazing
44:38 : uh yeah yeah look look look at the
44:43 : mandobrot set okay if you're in the mood
44:46 : for getting your mind blown I I did a
44:49 : couple of videos on that as well I I
44:51 : actually did some stuff on the Mando
44:54 : broad set which is pretty cool
44:57 : um
44:57 : okay getting back to this
45:00 : so
45:03 : um
45:05 : now with this obviously you it's very
45:08 : simple to change this to do it in the
45:11 : reverse order uh you just flip
45:15 : you do the right first and then just
45:17 : left after so you also know how to print
45:19 : the tree in reverse
45:22 : um
45:23 : I don't think there's a technical name
45:25 : for the reverse order
45:30 : um maybe they thought that was too
45:32 : trivial to to give it a name
45:35 : um but there there is a third type of
45:38 : tree traversal other than the pre-order
45:41 : and the in order okay uh
45:47 : uh so I guess if let me let me actually
45:50 : we never completed the pre-order so let
45:53 : me do that again so the pre-order would
45:55 : be like Jenny
45:59 : and then Jeff
46:02 : I think and then uh jam and then
46:06 : Jefferson
46:08 : and then uh yeah John
46:13 : and then drum
46:15 : and then Kenny that this this would be
46:19 : so
46:22 : this one is in order
46:25 : and this one is
46:29 : pre-order uh interestingly though this
46:33 : is a both of these are different order
46:35 : from
46:37 : my kill based one yeah I noticed that
46:41 : earlier so uh
46:43 : uh this I think is called a
46:48 : breath first
46:50 : I believe
46:53 : because it's interesting breath
46:56 : meaning
46:59 : it it's like it's doing level by level
47:03 : yeah so it
47:05 : [Music]
47:05 : um
47:06 : the word breast burst uh it's coming
47:10 : from the terminology of searching things
47:15 : uh which is in graph Theory so breath
47:19 : first search when you're searching a
47:22 : graph like for example in a social
47:25 : network I'm I'm trying to start from you
47:28 : go to all your friends go to each of
47:31 : their friends Etc to see if you're
47:35 : connected to Kevin Bacon right yeah
47:38 : uh and when you're doing that uh you can
47:43 : either do a depth first search or a
47:46 : breath first search uh oh okay Brett
47:51 : breath depth and breadth
47:53 : did I spell this wrong you spelled it
47:56 : wrong but I was thinking breath like
47:58 : breathing oh okay yes so I I was not on
48:02 : the right page breath okay gotcha like a
48:05 : term of measure what is that anyway I'm
48:09 : with you yeah you're with me okay so so
48:11 : what I'm saying is this is breaths first
48:13 : search which means you're not gonna do
48:16 : any of your friends friends until you've
48:19 : looked at every one of your immediate
48:21 : friends
48:23 : and and that's what this Q based
48:26 : approach would do which is different
48:28 : from either of these uh recursive
48:31 : approaches would generate
48:35 : um
48:35 : and and um
48:38 : there's one more one
48:42 : it's called a post order
48:45 : okay
48:46 : um the post order is
48:48 : I don't even know why would you would
48:50 : use this so I'll just include it for
48:54 : completeness I I it's just like you
48:58 : print yourself after you've done your
49:00 : children already
49:03 : so that would just mean I think you're
49:06 : gonna have print Jam first and then
49:09 : Jefferson
49:10 : and then you would print Jeff
49:14 : and then you would print drone and then
49:17 : you would print Kenny and then you put
49:20 : branch on and then finally you would
49:22 : print Jenny
49:24 : interesting that that's a weird way
49:27 : to do it and oh I can't think of a way
49:30 : or reason why you might do this uh maybe
49:33 : like
49:35 : maybe you wanna calculate
49:39 : something like
49:42 : um
49:44 : uh Helm like some statistic
49:49 : about
49:51 : hmm
49:54 : about each subtree like you you want to
49:58 : know
50:00 : how many
50:02 : uh how many descendants each guy has for
50:07 : example or or maybe like maybe each node
50:13 : has a score or something
50:15 : that you know is assigned in some way
50:19 : but but like if this was a social
50:22 : network which it isn't but if it were
50:25 : like every person has some popularity
50:28 : score or something yeah and then and
50:31 : then maybe you want to know
50:34 : like
50:36 : I wanna calculate the sum of the
50:39 : popularity scores
50:42 : of their friends friends
50:46 : Etc oh it it wouldn't work in this case
50:49 : because
50:51 : you would end up having Cycles
50:54 : like like Jung would end up connecting
50:57 : back to Jenny so you like Jung would
51:00 : also be a child of Jenny if they're a
51:02 : mutual friend relationships so maybe
51:04 : that's not a good analogy but maybe it's
51:07 : more like um
51:08 : organization an org chart in a company
51:11 : okay so this is the CEO and these are
51:14 : his managers and then we have team
51:17 : members Etc and then maybe each person
51:20 : has a score and then you want to sum up
51:23 : you know the sum of the scores at each
51:26 : level of the tree then you would want to
51:29 : get down to the leaves first to get
51:32 : their scores and propagate it up
51:35 : to this you know the next level and
51:38 : where it can be summed it summed and
51:40 : then uh and then propagate it even more
51:43 : up to the top
51:46 : yeah would it be used in like
51:48 : um
51:50 : so it doesn't react use tree structures
51:52 : or like not we're going to react to the
51:54 : dot like just the Dom yes the Dom using
51:56 : tree structures and I'm just thinking
51:57 : the language you're using is like events
51:59 : bubbling up to the top the parents to
52:02 : parents yeah it's used in that kind of
52:04 : context
52:05 : but I mean yes definitely the the dam is
52:09 : a tree
52:09 : and there's there's actually two ways in
52:13 : which the events can bubbling and bubble
52:16 : uh I think one is called
52:19 : capture face and the other one is called
52:24 : um
52:26 : oh I don't remember the other one
52:30 : the capture phase is like
52:34 : yeah so like if this were a Dom Street
52:39 : so
52:41 : so maybe like this is a Dev
52:45 : uh this is a paragraph
52:48 : there's a header
52:51 : and this is a span wait is this
52:55 : I don't know if uh maybe okay I don't
52:58 : think a header is supposed to be in that
53:00 : paragraph
53:03 : no uh okay
53:06 : it's okay it's an A and then uh Stan
53:12 : and then there's an image
53:14 : um so let's say if somebody clicks on
53:18 : this image right we have we have a click
53:26 : uh
53:28 : so what the browser has to do
53:31 : click
53:33 : that the way the browser figures out
53:35 : that you clicked on an image is if um
53:39 : well it has this tree structure but in
53:42 : addition to this tree structure it also
53:45 : needs to have
53:47 : the image coordinates and the rectangle
53:51 : for each element
53:53 : so like it needs to know that
53:57 : um
53:58 : in image terms
54:02 : maybe I am running out of drum
54:05 : but
54:07 : hold on move this away a little bit
54:11 : um so in image terms
54:14 : uh
54:16 : we have a diff
54:19 : actually the top thing is the diff this
54:23 : is the already the diff and then we have
54:26 : a paragraph one
54:28 : and we have paragraph two
54:31 : and then we're gonna have a
54:34 : link uh it's the link is gonna look like
54:40 : http
54:41 : blah.org
54:44 : and then we're gonna have uh hello world
54:49 : some text
54:51 : so this is the a
54:54 : um and then in the next one we have
54:56 : another span hello
55:00 : and then we actually have an image here
55:03 : oh maybe not an actual image but we have
55:07 : an image
55:11 : the
55:17 : okay
55:23 : this is an image so we click on this and
55:26 : the browser has to figure out well it
55:28 : your your position of your mouse
55:33 : uh
55:35 : the position of your mouse is within the
55:38 : rectangle of this the rectangle of the
55:41 : image element
55:45 : um but now
55:47 : but it's also within the rectangle of
55:50 : this paragraph element but it's also
55:52 : within the rectangle of the div element
55:56 : um so the question is how does it
56:01 : check does it need to check it for all
56:05 : three of them
56:06 : yes it does
56:08 : and in order in which order does it
56:11 : check
56:12 : so well
56:15 : since this is a tree
56:17 : it would make sense
56:19 : that it starts at the root of the tree
56:22 : so so it the browser actually doesn't
56:26 : magically know that it lands inside the
56:29 : image element
56:31 : the browser actually starts uh okay
56:34 : there might be ways it can manage to
56:37 : know that that but uh that's not the
56:40 : simplest way that that might be like the
56:43 : browser is trying to really go out of
56:45 : its way to be super fast there might be
56:49 : ways to do it like that but let's say
56:52 : we're not doing that but so uh we're
56:55 : gonna first check
56:57 : like we we got a click in this
57:00 : coordinate
57:02 : 56 70 or something like that and then
57:06 : we're gonna just check
57:07 : from the top of the tree is it in the
57:11 : rectangle of the diff well it is
57:14 : so if it is in the rectangle of the diff
57:17 : we keep going
57:18 : if it's not in the rectangle of the div
57:21 : that means you click outside of the diff
57:24 : there's no need to check any further we
57:27 : know we didn't click in any of the
57:29 : elements in the diff
57:33 : although that might also not be true
57:36 : when you have like fixed up or absolute
57:39 : positioning true true yeah but let's not
57:42 : worry about that for now let's see
57:45 : let's say our browser is uh doesn't
57:49 : support that kind of weird stuff
57:52 : um
57:56 : but uh so so then it's like okay yeah we
57:59 : clicked on the def
58:01 : now uh I can immediately fire a click
58:06 : event on the div element
58:09 : and uh
58:11 : right away
58:13 : and and then I'm going to track the
58:15 : children so uh so we're gonna so first
58:19 : check if click on this yeah if I did
58:22 : click on it so I'm gonna continue to
58:25 : find the most specific things in my uh
58:29 : descendants that it clicked on so first
58:32 : I'm gonna check the first p
58:35 : the first P well is this upper rectangle
58:39 : uh no we didn't click in the first P so
58:42 : there's no need to descend into each
58:45 : children so let's just try the second p
58:48 : we did click on the second p
58:51 : so I'm going to descend into each
58:52 : children
58:54 : um and go to this span that says hello
58:56 : no we didn't click on that span so you
58:59 : come back up
59:00 : and then we go to the image and then we
59:03 : say yeah we did click on
59:05 : this image and therefore we click on the
59:08 : image so here's the question
59:11 : um at what point in time do you fire
59:14 : that on click event
59:16 : and are we gonna fire it on click even
59:19 : on on the diff and the paragraph and the
59:24 : image oh probably yes because if if the
59:29 : programmer register on click event on
59:31 : any of these elements along the path we
59:34 : probably want to know divide them right
59:37 : okay
59:38 : but then the question is in what order
59:42 : should you fire them
59:44 : should you like if if the user
59:47 : registered on on click Handler for the
59:50 : paragraph and the image and the diff
59:54 : in what order should those three
59:58 : handlers be called should I call the one
1:00:02 : for the image first or the paragraph
1:00:04 : first or the diff first
1:00:07 : oh there's not no real right answer and
1:00:11 : we should probably just allow both ways
1:00:14 : to work
1:00:17 : and uh in in the browser there there is
1:00:20 : both ways you can it can work both ways
1:00:23 : when you add a listener
1:00:25 : you can choose to add it either to be
1:00:30 : triggered while it's traversing the tree
1:00:33 : on the way down or well it's coming back
1:00:37 : up
1:00:39 : so then you can get either order that
1:00:42 : you want
1:00:43 : cool