Tree and Graph Data Structures

# Traversing Nested Trees

Check out a free preview of the full Tree and Graph Data Structures course:
The "Traversing Nested Trees" Lesson is part of the full, Tree and Graph Data Structures course featured in this preview video. Here's what you'd learn in this lesson:

## Bianca uses recursion to live code a preorder traversal function for binary trees that prints the value of every node in the tree.

Get Unlimited Access Now

Transcript from the "Traversing Nested Trees" Lesson

[00:00:00]
>> Bianca Gandolfo: So then it gets real, families messy, things happen, you adopt a dog and then they have puppies. And,
>> Bianca Gandolfo: Now, we need to adopt this, so we're gonna just,
>> Bianca Gandolfo: Put this in here, and we are gonna play with this. So now, knowing that we have to account for the dog and her puppies and maybe we don't know how many puppies.

[00:00:42] This needs to be flexible for whatever, I guess we’re working ancestry.com and our users are inputting data about their family and we don't actually know anything ahead of time. So this is going to be a dynamic data structure that can have many children. Children can have children, children's children can have children, etc., etc., through whatever, Adam and Eve.

[00:01:04] So,
>> Bianca Gandolfo: What do we think?
>> Speaker 2: We can use recursion to call traverse for each of the children.
>> Bianca Gandolfo: Can we?
>> Speaker 2: I think we could.
>> Bianca Gandolfo: I think we could.
>> Speaker 2: And we wanna protect for lack of children, so we might wonder if statement back.
>> Bianca Gandolfo: Well, hopefully all of our children are also a tree.

[00:01:33] And we defined our tree to have a name in an empty child array. So they all should follow that. If for some reason it's not like everything explodes. We can pretend that we have checks, if we're writing a library. Yeah, we got to check all this stuff to prevent our consumers of the library from doing like all kinds of weird stuff.

[00:01:56] But if we're just doing it for ourselves and our small team, we can kinda like make assumptions here that they'll actually read the code, right? And library code, a lot of people don't look at that code, they just consume it. And then,
>> Bianca Gandolfo: Hope for the best. Okay, so we're going to do recursion.

[00:02:20] Where?
>> Speaker 2: After the console log.
>> Bianca Gandolfo: Here?
>> Speaker 2: In the forEach.
>> Bianca Gandolfo: Inside the?
>> Speaker 2: Yeah, in the forEach.
>> Bianca Gandolfo: Inside the forEach.
>> Bianca Gandolfo: What does that look like? Can someone tell me what?
>> Speaker 2: Maybe in place of the console log.
>> Bianca Gandolfo: Yeah,
>> Bianca Gandolfo: So you're saying?
>> Speaker 2: Just traverse value.

[00:02:43]
>> Bianca Gandolfo: Traverse.
>> Speaker 2: Val.
>> Bianca Gandolfo: Val, let's call this a child. Do you ever think of like a better name for something? Tell me, cuz when I'm talking about trees and presenting, like names, this is like the hardest thing. I get really creative when by myself making slides, but then when I have to do it live, it doesn't always work out.

[00:03:08] All right, so we're gonna traverse child.
>> Bianca Gandolfo: Do you think it's gonna work? Something else need to happen?
>> Speaker 2: Yeah, I'm bringing to get in to a infinite loop here without doing a base check of some sort, I mean.
>> Bianca Gandolfo: Let's [INAUDIBLE] think?
>> Speaker 2: Eventually, I try with have no children and will stop.

[00:03:28]
>> Bianca Gandolfo: Yeah, but that's good.
>> Speaker 2: Skip right in Europe.
>> Bianca Gandolfo: Yeah, yeah, yeah, [LAUGH] but this is a good consideration with recursion is we always need to make sure that there's some base case where it's going to stop. Otherwise it crashes your browser and that's annoying. I think Chrome handles it a lot better now.

[00:03:48] But sometimes it'll just cross the entire browser and you have to close it and then restart it, I don't know. Anyway, just always check, but I think we'll be fine. We're actually not even gonna run the code, we just run it in our minds. So let's do that, how do we run this in our minds?

[00:04:03] So we're gonna traverse with our family.
>> Bianca Gandolfo: And we're gonna do this sort of like create or execution environment and walk through what happens when we run this code, okay? So we passed family down, again, we have family here on the right. And the first thing we're gonna do is console log tree.name.

[00:04:26] What is gonna be printed? Someone who hasn't spoken much. I feel like Aisha, you've been quiet.
>> Bianca Gandolfo: You can also say pass.
>> Speaker 3: Yeah, one second, I'm processing.
>> Bianca Gandolfo: Sure.
>> Bianca Gandolfo: For here?
>> Speaker 3: Yeah, the tree.name.
>> Bianca Gandolfo: So this is our tree.
>> Speaker 3: Yep.
>> Bianca Gandolfo: What's .name?
>> Speaker 3: Gonna print Ashley.

[00:05:00]
>> Bianca Gandolfo: Ashley, well, console log Ashley, exactly. So we console.logged Ashley, great. Everyone's expecting that. Now, let's hop into our children loop. So for tree.children.forEach child, what is child here? The first iteration?
>> Speaker 2: Sammy.
>> Bianca Gandolfo: Yeah, probably Sammy, right?
>> Bianca Gandolfo: Here,
>> Bianca Gandolfo: And,
>> Bianca Gandolfo: Now, it gets interesting. So we say traverse with Sammy, right?

[00:05:45] So when I work with teaching recursion, what I like to do is whenever we recourse, I like to just copy and paste it. So this is Ash, we're friends now, I gave her a nickname.
>> Speaker 2: [LAUGH].
>> Bianca Gandolfo: This is a execution context, whenever you call a function, you create a new execution context.

[00:06:10] All of the variables and everything are brand new. They don't have any memory of what came before them, unless you're in a closure, but we're not worrying about that. Let's just deal with the facts. Okay, so now, tree is Sam, right?
>> Bianca Gandolfo: And which looks like this, right?

[00:06:33] This is a whole Sammy object, okay?
>> Bianca Gandolfo: It just console log, that,
>> Bianca Gandolfo: Okay, one of the main challenges of teaching coding is how to show it all on one screen with really big fonts. It's never ending.
>> Speaker 2: Really short variable names.
>> Bianca Gandolfo: Yeah, but then it's not as fun.

[00:07:02] Anyway, okay, so we have tree, an object called Sammy. What's gonna console log here? Who's next? Who said Ashley? Aisha, Sonny what do you think? We're here.
>> Speaker 2: That would be Sammy right.
>> Bianca Gandolfo: So we have this object named Sammy. And then Eric, we get to this, fun piece.

[00:07:38]
>> Speaker 2: We'd be looking at the object with the name Bowser, and we'd be calling the traverse function for that object.
>> Bianca Gandolfo: Yeah, so here's Bowser. So Bowser looks like this.
>> Speaker 2: So when do you get to Alex?
>> Speaker 2: Nobody cares about Alex.
>> Speaker 4: [LAUGH]
>> Bianca Gandolfo: Poor Alex. She can hear you.

[00:08:09]
>> Bianca Gandolfo: All right, okay,
>> Bianca Gandolfo: This is very interesting that.
>> Bianca Gandolfo: Anyway, these things are very useful when you're actually coding, but okay. So we have Bowser. What we need to do is we need to write this out, now this is Bowser tree.name, Michael?
>> Speaker 2: Yeah, so it'll log Bowser and then call traverse on the puppy.

[00:08:49]
>> Bianca Gandolfo: Make sure you're talking in the microphone.
>> Speaker 2: It'll print out Bowser and then it will do the forEach call traverse on the puppy, the P.
>> Bianca Gandolfo: Yeah, Pickles. Okay, so now we have traverse again,
>> Bianca Gandolfo: And this is gonna be Pickles, P for short. And now, we're gonna console log tree.name, what’s the name, Joe?

[00:09:31]
>> Speaker 2: Pickles.
>> Bianca Gandolfo: Pickles, exactly. And then what happens Michael here?
>> Speaker 2: Well, there's not gonna be any children on that pickles.
>> Bianca Gandolfo: Yeah.
>> Speaker 2: So you'll never fall into that forEach.
>> Bianca Gandolfo: So we skip over this, we never get there.
>> Speaker 2: Do you have to return?
>> Bianca Gandolfo: Well functions have an implicit return, what does a function implicitly return?

[00:09:58]
>> Speaker 2: Undefined.
>> Bianca Gandolfo: Undefined, so it returns for us. But you can also return something here, right? That's useful, for some cases, we might wanna return. Okay, but when we return, we pop off this execution context. And we come back here where we were with Bowser. So the next iteration of this loop,right?

[00:10:23] So we had traverse with Pickles. Now, we had to see if there are anymore children. Let's imagine that Bowser only had one puppy. And so this loop is over and then we have that implicate return. So we pop off this execution context and then we're back up here with Sam.

[00:10:45] So this was Bowser, soes Sam have any other children besides Bowser? No, so we're gonna pop that off. And then we're back here with Ash, so we traverse through Sam's family. Now, since we still have Alex left, we didn't forget about Alex, she's here. And we will traverse with Alex, and it's the same thing as we did before,

[00:11:23]
>> Bianca Gandolfo: tree.name is gonna be Alex. Alex doesn't have any children or pets. So implicit return,
>> Bianca Gandolfo: And we call it in.
>> Speaker 2: Is this the only way to transverse?
>> Bianca Gandolfo: No, there are lots of ways to traverse.
>> Speaker 2: But if you use that function then that's the only way to do it?

[00:11:47] That's how to go?
>> Bianca Gandolfo: I mean what we did is we just walked through how this code is executing in what order. But I mean, you can do interesting things, which we'll look at there. I think it's interesting, this is the beginning. We just need to understand this before we move on.

[00:12:04] Any questions?
>> Bianca Gandolfo: Do people feel better about recursion after seeing that, maybe?
>> Speaker 2: Yes, it was a good refresher. [LAUGH]
>> Bianca Gandolfo: Yeah, yeah, sometimes when I'm practicing, I actually just do that. Because I'll get confused, and it can get pretty meaty, and sometimes I'll just do that. Exactly, that's how I invented that is actually because that's just what I do when I'm trying to figure out why my code isn't doing what I'm expecting it to do.

[00:12:34] So feel free to use it, you can even use an interview context. Don't take as long as I do, but like super quick kind of trace through it.