Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Implementing a Tree" 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:

Now that Bianca has looked at the Linked List implementation, she spends a few minutes looking at how a Tree is implemented. The main difference between these two structures is a Tree cannot have any circular references. There is a root node in the tree and each node has a list of its children.

Get Unlimited Access Now

Transcript from the "Implementing a Tree" Lesson

[00:00:00]
>> Bianca: Took a little deep dive into link list and we're gonna circle back to Tree's. All right, let's take a look at our tree here. So what is the main difference between our tree here and a link list that we are implementing?
>> Male: Each node has two references.

[00:00:18]
>> Bianca: Yeah, so instead of just having one maybe .next, we have multiple, in this case we have two. But trees could be general, you can have like quad trees, so you can have a tree that has no specified number of children. So like one can have three, one can have one, one could have a million.

[00:00:38] You know, probably not super useful, but that would be like a general tree. What else?
>> Bianca: What's the same?
>> Male: Yeah, that is now called the root.
>> Bianca: Yeah, so we have a little bit of different vocabulary. The root is the same as our head, totally. What do we call our tail?

[00:01:06]
>> Male: Leaves.
>> Bianca: Leaves, can have multiple leaves, right?
>> Male: Mm-hm.
>> Bianca: But just one root.
>> Bianca: Cool, anything else?
>> Male: Do nodes hold references to their parents in the tree?
>> Bianca: Usually not, yeah.
>> Bianca: Cool, so one other tidbit about trees is that it's different than a link list.

[00:01:39] A link list can be circular, so a link list could actually point to itself, and that would be an okay thing. Where trees are not allowed to have a circular loop. So this, for example 13 couldn't connect to 12, that would be an incorrect implementation of a tree.

[00:02:00] Yup, cool. What else did I want to say about that? Yeah, so we hold references, usually from parent to child, similar to our single link, it's just one direction, except we have multiple nodes. And so back to our pseudocode,
>> Bianca: How is our constructor gonna be different?
>> Bianca: Maybe we can just copy what we have.

[00:02:37]
>> Bianca: And then we can put it here.
>> Male: So the node, instead of this.next for a node, you could do this, children and set up to an empty array?
>> Bianca: Yeah, yeah. So we wanna have a collection of children. And for a general tree, it could be an amount of children, right.

[00:03:07] We're not creating rules right now, but think about, if you did need to create rules with that it tells well, just in the back of your mind, cool.
>> Bianca: What else will be different? Would we have a tail, nope.
>> Male: Change head to root.
>> Bianca: Yep.
>> Bianca: Great.

[00:03:44]
>> Bianca: Cool, maybe want to add a node.
>> Bianca: What's the main difference here for adding a node?
>> Male: Well, we need more information because with the link list tallies, or you could assume it always goes on the end. But because we have branches here, we need to know where it goes.

[00:04:03]
>> Bianca: Mm-hm, yeah.
>> Male: Is that it?
>> Bianca: Yeah, but what about through the case where we have to loop? Link list it took us a second to figure out what kind of loop, but what if we needed to loop through, we call this traversing a tree.
>> Bianca: That presents a new kind of complication as well, right.

[00:04:25] Cool, awesome, so that's a cliff hanger. Cuz tomorrow we're gonna be traversing trees all over the place. And we're gonna hope into just creating your tree data structure. There's some exercises in there as well.
>> Bianca: Let's check it out.
>> Bianca: But the last two, the searching.
>> Bianca: You can see the note here.

[00:04:57] Hold off on DFS, and BFS, cuz we haven't covered that yet.
>> Bianca: Unless you know it and you just want to do it, go for it. We'll be doing it a few different times for a few different data structures.
>> Bianca: Cool, are you ready? So now, armed with our knowledge, we're going to implement a tree.