Transcript from the "Review: Trees Part 1" Lesson
>> Bianca Gandolfo: So we looked at the linked list, but we did not look at the tree yesterday. The interesting thing that I wanted to point out about our tree versus our linked list. So a link list is a type of tree it's a simple tree that has one child.
[00:00:12] And this is a general tree called an N-ary tree, right, you've heard of a binary tree. That means there's two children N-ary means there could be N number of children, so general tree. It's not the most useful tree because of that, but it's a good intro into trees.
[00:00:27] So the difference between our linked list and our tree is that, we call them nodes, but instead of,
>> Bianca Gandolfo: How do I say this. Instead of having its own constructor, each node we consider it a tree. And so we just, as we add a node, we're just adding trees.
[00:00:55] So each node is in itself a tree.
>> Bianca Gandolfo: Yeah, and as you save your instance of a tree, as you add a child this instance is going to be your root node.
>> Bianca Gandolfo: That make sense?
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: Why is this different than a linked list? And why do you think linked list we had a node constructor and then we had a linked list constructor?
>> Bianca Gandolfo: When this we don't?
>> Speaker 2: One child versus multiple children.
>> Bianca Gandolfo: Yeah, there's that. But couldn't we just have a node that instead of saying, null, it's just an array? So the .Next can be an array.
>> Bianca Gandolfo: There is no reason it couldn't be.
>> Speaker 3: But then that array each element can have another next right?
>> Bianca Gandolfo: Yeah, I mean so you don't wanna make a linked list like that but you could and it wouldn't break it.
>> Speaker 3: In that case the array itself would have a .Next property or each element in the array would have .Next properties.
>> Bianca Gandolfo: I don't know, let me think.
[00:02:27] So if we had a linked list and we had the .Next as an array, then yeah the array would have it's own .Next. So it would be like array.next.
>> Speaker 3: Okay.
>> Bianca Gandolfo: Yeah.
>> Speaker 3: Not each element?
>> Bianca Gandolfo: Not each element within the array.
>> Bianca Gandolfo: This is hypothetical, this is not a good implementation.
>> Speaker 3: So the question is, why was our linked list constructor as well as a-
>> Bianca Gandolfo: Yeah, as well as a node constructor. The simple answer is, is for a tree all we need is the value and the children for our linked list. We have pointers to both a head and a tail within our data structure.
[00:03:17] And so because of that, it makes sense to separate it, right? Cuz each node of a linked list doesn't have a head and tail, however each tree has a value in an array of children.
>> Bianca Gandolfo: So you could do it, if you did implement it by making each node part of the tree, you might realize that in your tree constructor, it would just be kind of empty.
>> Bianca Gandolfo: Right, because what that would look like.
>> Bianca Gandolfo: Right we have function Node, the value.
>> Speaker 3: I'm thinking maybe the reason we want to separate the node from the linked list is that in a linked list we wanna keep track of where the tail is. And in a tree there are many leaves, so it's not practical to keep track of all the leaves.
>> Bianca Gandolfo: Yep, yeah, absolutely. So it all has to do with this extra this.head.
>> Bianca Gandolfo: this.tail, right this extra metadata that we want just on the parent's data structure, right not each node. So for this case, for this particular tree we don't need metadata, all we need is the value and the children.
>> Bianca Gandolfo: So, we don't need to have an external node creator cuz each node is a tree, there's no metadata needed.
>> Bianca Gandolfo: Can I have one question about that?
>> Bianca Gandolfo: You can just humor me with a question, if you already know the answer.
>> Speaker 3: Is there a limit on the number of children that a tree can have?
>> Bianca Gandolfo: Not this one.
>> Speaker 3: Do you need to keep track of the very first root?
>> Bianca Gandolfo: Yeah, so the root is just gonna be here, it's just gonna be this. The instance is your root.
>> Speaker 3: From looking at just a tree object, is there a way to tell if it's the root?
>> Bianca Gandolfo: So, it's the root if it doesn't have any parents. And if your tree doesn't have a reference to its parent, which usually it doesn't, it's hard to know if it's explicitly the root, so yeah.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: So to add a child, where we're gonna put it on the prototype.
[00:06:25] We're gonna instantiate a new tree, and we're gonna push it to the children array, and then maybe we'll return it.
>> Bianca Gandolfo: Cool, anyone do it differently?
>> Bianca Gandolfo: No, everyone do this exactly like this?
>> Speaker 3: I indented that with four spaces instead of two, that's the only difference. [LAUGH] It's a hard different so well, spark debate world wide.
>> Speaker 2: It could be worse, you could have used tabs.
>> Bianca Gandolfo: I know.
>> Speaker 3: Instead of child I named variable sub tree.
>> Bianca Gandolfo: Sub tree? Cool.
>> Bianca Gandolfo: It's a good name for it.