# Binary Tree Traversal: Part 2 (with Recursion)

Published on May 28th 2023Duration: 1:00:45Watch on YouTube

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: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: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: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
• 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: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: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: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