Data Structures and Algorithms in JavaScript

# Pseudocoding In-Order Traversal Part 1

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 1" 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 starts pseudocoding the in-order traversal algorithm for a Binary Search Tree. The in-order traversal algorithm will search to the left most node before traversing back to the right. Once the pseudocode is written, Bianca begins tracing out how it would execute with an example Binary Search Tree.

Get Unlimited Access Now

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

[00:00:00]
>> Bianca Gandolfo: So we're going to pseudo code this out. We're going to talk about pre-order, post-order, and then I'm going to set you free to work on it on your own. And then we'll come together, we'll pseudo-code it out again, and then we'll go through the solutions. So first go all the way to the left, then you wanna do, what would be the English word for this?

[00:00:29] Go all the way to the left, and then I guess the parent, then the right, then the parent parent, something like that?
>> Bianca Gandolfo: Is this making sense? So we go all the way to the left.
>> Abby: Yeah.
>> Bianca Gandolfo: Then the parent is five, then the right, and then the parent parent is seven.

[00:00:55]
>> Bianca Gandolfo: Is that clear? Okay, so those are just our notes, okay.
>> Abby: How do you get all the way back up and to the left?
>> Bianca Gandolfo: Let's see, we're going to explore that right now. So, who here thinks this is recursive? I do, awesome, cool. So we'll just call this traverse, to make it easier.

[00:01:32]
>> Bianca Gandolfo: So,
>> Bianca Gandolfo: We're gonna traverse.
>> Bianca Gandolfo: What do you think our base case would be,
>> Bianca Gandolfo: For-
>> Abby: [INAUDIBLE]
>> Bianca Gandolfo: Yeah.
>> Abby: There aren't any words [INAUDIBLE].
>> Bianca Gandolfo: To the right?
>> Bianca Gandolfo: Traverse when you are a leaf, maybe. Maybe, can explore what that's like. So a leaf is anything that doesn't have a child on the left or the right.

[00:02:12] So, maybe we'll just stop, cuz we need a return out of our recursion, and that's how we're gonna jump backup levels, is once we return, that's a spoiler.
>> Bianca Gandolfo: So, maybe our base case it's a traverse when you're a leaf. Does anyone have any other suspicions,
>> Bianca Gandolfo: Of when we would stop?

[00:02:52]
>> Bianca Gandolfo: No, okay, we could try that one out. This is how we figure out a solution, we come up with a hypothesis, and then we test it. We're like computer scientists or something, I don't know, okay. So, what would be the next thing that we do? So we're like, okay, we have this hypothesis for a base case.

[00:03:15] And then maybe there's something where you have to break down the problem smaller, so that it reaches closer to the base case, it's our thing in recursion that we do. What would be a way to do that?
>> Speaker 3: [INAUDIBLE]
>> Bianca Gandolfo: Yeah, so you can break it down by saying this.left.

[00:03:45] Then we have this.value, right, which is the current, then we have this.right. Those are our main pieces in question, so ideally, we wanna go left, current, right. So here we have left, current, right, that's the order, recursion's gonna happen. On which pieces of these does the recursion happen?

[00:04:08]
>> Abby: Left.
>> Bianca Gandolfo: What else?
>> Abby: Right.
>> Bianca Gandolfo: Mm-hm.
>> Bianca Gandolfo: Okay, and then we say when there's like no, this.left or this.right, maybe return that would be like, or and, that would be our base case. Obviously there's no when in JavaScript that's just pseudo code. What do we think?

[00:05:01] Should we try it with some numbers and see what happens? Okay, here we go.
>> Bianca Gandolfo: It's the hover.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: My sneaking suspicion is it would work either way, but sometimes it's not worth it with JavaScript, it's too lenient, okay.
>> Bianca Gandolfo: There we go, now can look at our picture at the same time.

[00:05:35]
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: Great,
>> Bianca Gandolfo: So our current is gonna be 11, so this.val
>> Bianca Gandolfo: Is 11, right?
>> Bianca Gandolfo: Cool, so we're gonna play that game, that popcorn game where you get to say what happens next.
>> Bianca Gandolfo: You guys remember that game that we played, where we went through and we said this is what happens next?

[00:06:09] We pretend where the JavaScript engine, or whatever?
>> Speaker 4: Yes.
>> Bianca Gandolfo: Get excited about it, you get to be a JavaScript engine, just like you always wanted! Okay, so John, do you wanna go first?
>> John: So first it's going to check to see if there's a left or a right, and since there is, it's going to move on.

[00:06:43]
>> Bianca Gandolfo: Cool, Abbey, you want to go next?
>> Abby: Are we like doing the things, or do we just?
>> Abby: Or, cuz, okay.
>> Abby: So it's going, I mean, it's continuing on in the left one.
>> Bianca Gandolfo: Yeah, so we're gonna call recursively.
>> Abby: Yeah.
>> Bianca Gandolfo: So what is this.left?

[00:07:07]
>> Abby: This.left is, if we're starting at 11?
>> Bianca Gandolfo: Mm-hm.
>> Abby: this.left is seven.
>> Bianca Gandolfo: Yep, so, and maybe I can do this, this is our, remember that's like where, that's where we stopped and left off before.
>> Bianca Gandolfo: So this.val is what now?
>> Group: Seven.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: Andy?

[00:07:37]
>> Andy: So now it's seven and the left and right are not null.
>> Bianca Gandolfo: Mm-hm.
>> Andy: So we traverse the this.left.
>> Bianca Gandolfo: Cool, and Miranda you're up.
>> Miranda: So, now it's 5.
>> Bianca Gandolfo: Mm-hm.
>> Miranda: And again, we're not null, so we're going to traverse this.left again.
>> Bianca Gandolfo: Yep,
>> Bianca Gandolfo: Okay, so we're leaving off here somewhere.

[00:08:25]
>> Bianca Gandolfo: And then Jen, what's our current value then?
>> Jen: 3.
>> Bianca Gandolfo: Then what happens?
>> Jen: That friendly evaluates, yay!
>> Bianca Gandolfo: So it returns, and then what happens when we return?
>> Jen: Pops off.
>> Bianca Gandolfo: Pops off the stack, yeah.
>> Bianca Gandolfo: So we pop.
>> Bianca Gandolfo: And then we come here, and we continue executing.

[00:09:01]
>> David: And we have a bug, though, that if 5 is right, sorry.
>> Bianca Gandolfo: We're going to get there, you're so good, we're going to discover it, no, no, it's okay.
>> Abby: Are we aggregating anything?
>> Bianca Gandolfo: You don't need to, we're just going to put exclamation points at the end, but I think you're onto it too.

[00:09:23] You guys went quick, okay, so we stopped where we left off. We just returned nothing, right, so this is undefined, maybe. And then we go to this.val, what is this.val in this frame?
>> Abby: Five.
>> Bianca Gandolfo: Five, this is where we wanna put our exclamation points, right, probably?
>> Abby: Yeah.

[00:09:45]
>> Bianca Gandolfo: Cuz we did 3, and then we did 5, so we probably have some function that does some transformation.
>> Bianca Gandolfo: Is that clear?
>> Bianca Gandolfo: And then what happens, David?
>> David: I think I was distracted.
>> Bianca Gandolfo: We just did this.
>> David: We just, okay, so we, we just returned the 5, so then we need to-

[00:10:14]
>> Bianca Gandolfo: We just yeah, we didn't return it.
>> David: Return it, we called, whatever, all right, we did the five. So then we need to transverse the right, which is labeled 6.
>> Bianca Gandolfo: Yep, so that means we call function again. Timbit, what's our value?
>> Timbit: Six
>> Bianca Gandolfo: Six, yep, then what happens?

[00:10:41]
>> Timbit: Hit returns, that would be true?
>> Bianca Gandolfo: Yep, returns.
>> Bianca Gandolfo: Then,
>> Bianca Gandolfo: John, what does it mean when you return?
>> John: You pop it off.
>> Bianca Gandolfo: Pop it off.
>> Bianca Gandolfo: And Abby, what do you think happens after this? So we just popped this off
>> Abby: You popped off 6?

[00:11:13]
>> Bianca Gandolfo: Yeah, so we called this and we popped it off.
>> Abby: So, it's supposed to go back up to 7 after that, right?
>> Bianca Gandolfo: Mh-hm, but what is actually happening? Now, why is it supposed to happen? Once you reach the end of a function, do you know what happens automatically?

[00:11:32]
>> Abby: It returns undefined.
>> Bianca Gandolfo: Mh-hm, so what happens when you return from a function?
>> Abby: It pops off the stack.
>> Bianca Gandolfo: Yep, pops off the stack.
>> Bianca Gandolfo: So then we'll continue from where we left off. Andy?
>> Andy: Yes.
>> Bianca Gandolfo: What happens next?
>> Andy: We'll do our function on this.value, which is 7?

[00:11:59]
>> Bianca Gandolfo: Yep, and we'll give it some exclamation points. And then Miranda, what happens next?
>> Miranda: You go right?
>> Bianca Gandolfo: Yep, we go right, and you can imagine this is gonna keep drilling down, right? So let's just keep going.