Data Structures and Algorithms in JavaScript

# Pseudocoding In-Order Traversal Part 2

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 "Pseudocoding In-Order Traversal Part 2" 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:

## Bianca continues using the in-order traversal pseudocode to talk through an example Binary Search Tree. She traces out each step along the way and talks briefly about how in-order traversal compares to pre-order and post-order.

Get Unlimited Access Now

Transcript from the "Pseudocoding In-Order Traversal Part 2" Lesson

[00:00:00]
>> Speaker 1: Actually I have a question about that though. You're going right, then you need to go left again.
>> Bianca Gandolfo: Yep, cuz you're gonna, so once you traverse, what happens is, it's gonna call this whole thing again, so it's gonna go both left,-
>> Speaker 1: Right, okay.
>> Bianca Gandolfo: And right.

[00:00:13]
>> Speaker 1: Yeah.
>> Bianca Gandolfo: Just at 7, it's not gonna go left anymore from 7, cuz we already did that.
>> Speaker 1: Yeah, at that point.
>> Bianca Gandolfo: It's only gonna go to the right.
>> Speaker 1: Okay.
>> Speaker 3: At that point we go to the right. We get nine, right?
>> Speaker 1: Mm-hm.
>> Speaker 3: And then how do we go-

[00:00:33]
>> Bianca Gandolfo: Back to 11?
>> Speaker 3: Just after nine, we have to go to eight, or just?
>> Bianca Gandolfo: Yeah, well first you go to eight, actually you want to go all the way down to the left, and we can assume that if it did that for this left subtree, the behavior is going to be equivalent on this right subtree, because it's recursive and they're trees, and that we can just trust.

[00:00:58] Same if it happened on this subtree like that, we can also trust that it happened on this subtree, the entire one, and even bigger. It's a trust we have to have in our heart.
>> Speaker 3: [LAUGH] How-
>> Bianca Gandolfo: It's easier for some people than others. But there is a bug that David pointed out.

[00:01:34] So the point was, I wanted all of my data to be exciting.
>> Bianca Gandolfo: So what did we put exclamation points on?
>> Speaker 4: Everything but 11.
>> Bianca Gandolfo: So far, I mean, we did 7. What's the other one that we did?
>> Speaker 4: Five. Three.
>> Bianca Gandolfo: Five. How many nodes did we look at though?

[00:02:07]
>> Bianca Gandolfo: So what's going on?
>> Speaker 1: We need to call the function again at the end? After the right.
>> Bianca Gandolfo: Mm-hm. How do we know that we've made it that far?
>> Bianca Gandolfo: So we didn't call it on three, and we didn't call it on six. Why not?
>> Speaker 4: They have to be returned?

[00:02:32]
>> Bianca Gandolfo: Yeah, cuz it returned. Exactly. So how might we fix that?
>> Speaker 1: Could you return the function? If bang, bang, whatever, if this left is not null, then traverse left, and if this right is not null then traverse the right, and we don't need the other check.
>> Bianca Gandolfo: What do we think?

[00:03:11] How does that change things? So you're suggesting we just get rid of our base case?
>> Speaker 1: Just say, yeah, if{!!this.left} traverse{this.left}.
>> Speaker 1: I don't know how you read that, yeah.
>> Bianca Gandolfo: Cool. Double bang. Double bang.
>> Speaker 1: Bang bang sounds more violent.
>> Bianca Gandolfo: [LAUGH] Bang bang.
>> Speaker 1: Bang bang.

[00:03:36]
>> Bianca Gandolfo: Cuz I just got right. Traverse right.
>> Bianca Gandolfo: All right party people.
>> Speaker 1: But we would still need the when.
>> Bianca Gandolfo: Still need- For the-
>> Speaker 4: Leafs. We distributed the base case.
>> Speaker 1: Well if you're at a leaf you're not going to recurse, because both conditions will fail.

[00:03:59]
>> Bianca Gandolfo: Yeah. Mm-hm, and where's the return happening then?
>> Speaker 1: Returning undefined.
>> Bianca Gandolfo: Yep, so it's just gonna return here, cuz that's just what happens magically.
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: All right, so that's our in-order traversal.
>> Speaker 3: The function that you're passing your values to is just an aggregating function?

[00:04:51]
>> Bianca Gandolfo: I mean, what are you aggregating exactly? When you mean aggregate, do you mean like you're adding stuff together?
>> Speaker 4: Yeah, well, what is the, what, I guess I don't understand what the return value of this is supposed to be. The whole process.
>> Bianca Gandolfo: Nothing.
>> Speaker 4: Nothing?
>> Bianca Gandolfo: Yeah.

[00:05:06]
>> Speaker 4: You just wanna go through all the nodes and that's it?
>> Bianca Gandolfo: You wanna go through all the nodes and run a function on it.
>> Speaker 1: Yeah so, it might be pushing it onto an array-
>> Speaker 4: So it's like a transformation.
>> Bianca Gandolfo: Exactly.
>> Speaker 4: Okay.
>> Bianca Gandolfo: So we're transforming all of our numbers to have exclamation points.

[00:05:18]
>> Speaker 4: That's what I-
>> Bianca Gandolfo: Hypothetically.
>> Speaker 4: That's what I was missing. Okay, I thought that it was something like you were trying to push each of them onto an array, or like add them to something, or-
>> Bianca Gandolfo: Yeah, maybe you could do that.
>> Speaker 4: Which you could.
>> Bianca Gandolfo: But that was, so, if you are going to return the value out of this,-

[00:05:36]
>> Speaker 4: Yeah.
>> Bianca Gandolfo: You need to change a few things around.
>> Speaker 4: Right.
>> Bianca Gandolfo: Like, if your function is going to return something, you need to account for that return value. Right now, this is just gonna let you do side effects.
>> Speaker 4: Right.
>> Bianca Gandolfo: So-
>> Speaker 4: Yep, okay. That makes sense.

[00:05:53]
>> Bianca Gandolfo: Yeah, okay. So,
>> Bianca Gandolfo: That's in-order traversal. We did that, it's quite elegant.
>> Bianca Gandolfo: Pre-order traversal.
>> Bianca Gandolfo: You guys ready for this?
>> Bianca Gandolfo: So the pre-order traversal runs it on the parent before going to the child.
>> Bianca Gandolfo: Cool? So if you could see here, the arrow is saying that's the order in which the function is called.

[00:06:36] It's not actually the order in which it's visiting, necessarily.
>> Bianca Gandolfo: Cuz, right, we had to drill down in our recursive calls kind of, to get down to the bottom. So we're not actually skipping anything, because we can't do that.

[00:06:58] Then 7, 5, 3, 6, 9, 8, 10, [SOUND] 15, and then the same.
>> Bianca Gandolfo: So what order is this in? I already kind of told you, but if you had to sum it up on your own?
>> Speaker 4: It's in ascending order by parent, kind of.
>> [INAUDIBLE]
>> Speaker 4: Parent, yeah.

[00:07:37]
>> Bianca Gandolfo: So it first looks at itself, or the parent, and then it goes which way?
>> Speaker 4: Left.
>> Bianca Gandolfo: Left?
>> Bianca Gandolfo: And then it looks at? Self.
>> Speaker 4: Self. Left.
>> Bianca Gandolfo: Right.
>> Speaker 4: Right.
>> Bianca Gandolfo: Right.
>> Speaker 4: Right, right.
>> Bianca Gandolfo: Left, right.
>> Speaker 4: Yeah, right, left, right, right, left.
>> Bianca Gandolfo: So part of your task here is pseudo coding it out, just like we pseudo coded out the in-order, for both the pre-order and the post-order.

[00:08:24]
>> Bianca Gandolfo: Cool? So what's post-order?
>> Speaker 4: Children first?
>> Bianca Gandolfo: Mm-hm.
>> Bianca Gandolfo: Cool, so I'm gonna set you free. So let's talk about what in-order traversal is. So remember, trees, we can only go from the parent to the child, right? That's the only way we can traverse, and I'm still laughing about my thanks, yo mama joke.

[00:08:51]
>> Speaker 1: [LAUGH]
>> Bianca Gandolfo: I've got to get over [LAUGH] it. So that's the only way you can do it. So we have to start at our root, and we need to get down to 3, and then we want to go to 5, 6, 7, 8, 9, ten10 etc., because we want to visit our nodes in order, okay?

[00:09:14] So, knowing that we can only visit from our parent to child, and we have two options right, we have left or right, first one seems to me that we would have to go left, right, and these are recursive calls, and so, if I was personifying a tree, here I am, an in-order traversal tree, what I would do is first, I wold start at 11, cuz that's what you have to do, and then 7, going down, getting shorter, then 5, and then 3.

[00:09:49] Once we hit 3, we wanna call the function, right, cuz we wanna call the function to everything, and then once we're done with that, we're gonna go back up to our parent, how do we go back up to our parent? We have to return from our recursion, somehow return another function.

[00:10:09] So then we call the function on 5, and then we need to go right, to 6. So once 3, 5, and 6 are good to go, we're gonna return again up another layer, to 7. We call, so from 7, we're we left off, we went left. So once we return out of our left recursion, we come back to ourself, call our function on ourself.

[00:10:42] Then, we're gonna go right. So the pattern here is left, self, right.
>> Bianca Gandolfo: Cool? So left, self, right. That's our pattern. Cool.