This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Pre-Order Traversal" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

With pre-order traversal, rather than traversing to the left-most node first, the algorithm begins with the current node. After the current node is visited both left and right children are visited. Bianca modifies the in-order pseudocode to become the pre-order algorithm to further examine this difference.

Get Unlimited Access Now

Transcript from the "Pre-Order Traversal" Lesson

[00:00:00]
>> Bianca Gandolfo: So let's look at this pattern. Can someone identify the pattern for me?
>> Speaker 2: It's an act, then left then right.
>> Bianca Gandolfo: Yes.
>> Speaker 2: Or self act, then left then right.
>> Bianca Gandolfo: Yeah, let's test it out. So self 11, then we go left to 7. Once we're on 7, the column on self and then we go to five to the left, right?

[00:00:23] Self, three, self and return and relief, and then we go back up. We already called on self, so then the next one is right. So self, left, right. And you might notice that it's easiest to kind of see that in this leftmost. Little subtree, so we have self, left, and then right.

[00:00:48] And because it works on one little subtree it's gonna work on the bigger subtree. And the big momma subtree of all subtrees or the entire tree actually. Unless it's a subtree, cuz I don't know where this arrow is coming from. That's pre-order, so when we set the order for post order it was left self right.

[00:01:13]
>> Speaker 3: In order.
>> Bianca Gandolfo: Sorry, in order left self right. Okay, in our code kinda looks like that, in our pseudocode. Let's see if I still have it. Left, self, right. So pre order, let's try to pseudocode out our pre order. I'll put it over here
>> Bianca Gandolfo: So those are post-order, but we'll leave it up there for reference.

[00:01:52]
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So what's the pattern?
>> Speaker 2: For pre-order?
>> Bianca Gandolfo: Yep, Self.
>> Speaker 2: Self
>> Bianca Gandolfo: Left.
>> Speaker 2: Left.
>> Bianca Gandolfo: Right.
>> Speaker 2: Right.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: So how in this pattern up here, let's do,
>> Bianca Gandolfo: Left, Self, Right. So this is in order,
>> Bianca Gandolfo: And then we have our Pre-Order.

[00:02:29] Smiley face just cuz why not. It's 3 o'clock on a Thursday. Smiley o'clock somewhere. Okay, Self, Left, Right.
>> Bianca Gandolfo: Can anyone guess? We have a pattern up here.
>> Bianca Gandolfo: How do we apply the pattern?
>> Bianca Gandolfo: Mm-hm?
>> Speaker 3: You mean for post, or for just pseudocode in this one?

[00:02:56]
>> Bianca Gandolfo: For a pre-order.
>> Speaker 3: For pre-order, it would just be you would use your function first. And then you would traverse left and traverse right?
>> Bianca Gandolfo: Yeah, exactly. So here we have go left,
>> Bianca Gandolfo: And then we, this is Self, right? And you can almost just copy and paste this over.

[00:03:22]
>> Bianca Gandolfo: So we need to start with Self. Then we go left. And then we wanna go right.
>> Bianca Gandolfo: Does anyone not believe me?
>> Bianca Gandolfo: Sometimes there's disbelievers in the world, and I accept all faiths.
>> Bianca Gandolfo: But you can join my cult any day.
>> Bianca Gandolfo: Just kidding, I would never do that.

[00:04:02] Okay, or would I? I don't know.
>> Bianca Gandolfo: I don't know, I'll let you guys, let that percolate.
>> Bianca Gandolfo: Okay,
>> Bianca Gandolfo: Do you guys wanna do the thing that we do? Our stack thing? Or are we good? Stack thing, or are we good?
>> Speaker 3: Good. I'm good.
>> Bianca Gandolfo: Good?

[00:04:28] Everyone's good?
>> Speaker 2: Two thumbs.
>> Bianca Gandolfo: Two thumbs if you're good. MIddle thumb if you want me to do the stack thing. Middle thumbs? Okay, we'll do it quick. Okay, so we have the value Starts at 11. Let's start at 5 just to make it small. So our value is 5.

[00:04:49] We enter into this function. The first thing we do is call in on 5. We have our happy //5!!! Then, we traverse on left. So this is saying if there's a left. This is coming up a lot. You can totally do this and it's fine. It does the same thing as far as I'm concerned.

[00:05:13] So if this is true, then you are going to traverse left. So when we traverse that's a recursive call, we're gonna Stop here. And we're going to put our
>> Bianca Gandolfo: Function here. So,
>> Bianca Gandolfo: We just called this.left. What is this.left? Timbe, do you know?
>> [INAUDIBLE]
>> Bianca Gandolfo: 3, absolutely.

[00:05:47] So the value here in our next call is gonna be 3. So then we call the function. So now we have a super-happy 3, all the smileys. And then, is there a left? Nope. Is there a right?
>> Bianca Gandolfo: From three.
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Does three have a this.right?

[00:06:09] Nope. So then we do what? When come to end of function or return we, we should all say together.
>> Bianca Gandolfo: Pop it off the stack, yeah. I know it's late in the afternoon.
>> Bianca Gandolfo: Tough lives we have here. Cool. So we popped it off the stack. We come where we left off.

[00:06:36] So we left off there. And again, we're back at five cuz we've popped out the stack. We're in the next level above. The very next line of code we say, is there a right? Does five have a right? Yes. So let's traverse there. And the value is six, right?

[00:06:56] And then we do the thing Here's a thing that we do.
>> Bianca Gandolfo: So our value is 6, put some exclamation points. Does 6 have a left? Nope, does 6 have a right? Nope. We come to the end and then we just return the heck out of there, right?

[00:07:15] Out of there, out of there, out of there. And now, we left off here, remember?
>> Bianca Gandolfo: We're done, and we pop off this stack.
>> Bianca Gandolfo: To the next level, what's the next level? Seven.
>> Speaker 2: Seven.
>> Bianca Gandolfo: Seven, exactly, and then we would go to sevens right. Straight from there.

[00:07:48]
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: Do we get it? Great. So that's pre-order, self, left, right, self, left, right. Again we can pick here to kind of get a more and easier to understand perspective, self, left, right? You do a dance with it too, that's some hip so it makes you remember