This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Depth-first Traversal Solution" Lesson
[00:00:00]
>> Brian Holt: We're going to go implement these three different traversals. And hopefully seeing all three of them side by side you'll see that they're relatively similar. It's just really reordering the statements, right? So if you remember doing recursion from part one, the first thing that you always do when you're doing recursion is base case, right?
[00:00:24] Figuring out what's your base case is. So there's a couple ways of doing it. The way that I prefer to do it which makes the code a little bit simpler. Is I say if node is undefined or null or anything like that, then just return, right? So that's what I'm gonna do here, so if no node, then just return array.
[00:00:44] And that's it. That we we don't have to do any other checks. We can just pass anything in. And we'll be sure that if node is not actually no, then it's just going to return. So first thing we're gonna in pre-order, right, is we're going to process the node, right?
[00:01:05] So we're going to do array.push(node.value), okay? Then what we're going to do in pre-order traversal is process the left tree. So we're going to call array = preorderTraverse(node.left, array); right? Then we're gonna do the same thing with node.right and then we're going to return the array. Now, when my right leaf points out that I am operating on the array so its actually not entirely necessary for me to return the array.
[00:01:58] That's just force of habit on my part, but if you don't feel like doing that, that's fine, too, so.
>> Brian Holt: So let's just go down and make sure that I'm not crazy, which this will definitively prove that I'm not.
>> Brian Holt: But we should see here that preorderTraverse is working as expected.
[00:02:21] Cool?
>> Brian Holt: So now that we've coded one of these they're all pretty similar, right? They're more or less doing the same thing and we're just reordering them in some sense. So in this particular case, does this work? Nope, it doesn't, not in CodePen. But what I'm going to do is I'm just going to move array.push between the two.
[00:02:46]
>> Brian Holt: And that's what inorder traversal is, right? This one you're gonna process the node first, right? This one you're gonna process in the middle. And spoiler alert, this one you process it last, right? But let's go take a look and make sure that that's actually the case.
>> Brian Holt: It's not, apparently.
[00:03:11]
>> Speaker 2: You didn't change the function names.
>> Brian Holt: I didn't. You're right. The dangers of copy paste code. Never done that before. Cool, so that works.
>> Brian Holt: Lastly we're gonna do post order traversal, this time learning from my mistakes.
>> Brian Holt: Okay, so here I changed it to postorder, postorder.
[00:03:44] And then the last thing I do is add it to the array. We'll go down here and remove the x.
>> Brian Holt: And we'll try running it again.
>> Brian Holt: And now we have all three. In pre-order, in order, and post order traversal.
>> Brian Holt: Questions? It makes sense?
>> Brian Holt: I see people kinda like just tilting their heads.
[00:04:14] [LAUGH]
>> Brian Holt: So. [COUGH]
>> Brian Holt: Hopefully this at least illustrates to you the kind of thedifferent strategies for processing a tree in some capacity