Tree and Graph Data Structures Tree insert Solution
Transcript from the "Tree insert Solution" Lesson
>> Bianca Gandolfo: Let's take a look at our solution. So in our constructor, we have two properties. We have the value, so whatever restoring in that node, whether that's a question, right? Or it's the name of a person or a number. So we have the value and then we have the children.
[00:00:22] So each node has children and we're just gonna initialize that as an MT array. And so that is the basics of our tree. So what our constructor does is whenever we do something like this, new Tree, it's gonna return an object that meets this. So if we're gonna say, let's move over here.
[00:00:50] So let's say. We're gonna say.
>> Bianca Gandolfo: I don't want that. Say, myTree = new Tree. So we're gonna initialize our new Tree like this. If we then console.log(myTree), it would look something like this, it would be an object. We'd have a value, what would the value be?
>> Speaker 2: 1?
>> Bianca Gandolfo: 1, what else would be on it, what's the other property?
>> Speaker 2: Children empty url
>> Bianca Gandolfo: Children. So this is your tree. Your tree is one node with the value one and its has no children, cool. Does anyone have questions about how we got here?
>> Bianca Gandolfo: Yes.
>> Speaker 2: I have a question about the return in the insertChild function, why are we returning the new Tree if in the step above we're pushing it into this.children.
[00:01:56] Why do we need to return it?
>> Bianca Gandolfo: You don't need to. Like the way you define your API is based on whatever your use case is. And so you don't have to it depends. So if you want to model this after how you interact with an array. So if you push a value into the array, it will actually return the length.
[00:02:19] Not really useful for this, returning the node that you just created will also give you reference to it so then you can, and that's why I do it here, so that you have reference to it so that you can do work on that. Yeah.
>> Speaker 2: Thank you.
>> Bianca Gandolfo: Mm-hm, for sure, okay.
[00:02:41] So, this is initializing our tree. And when we insert a child, what we're doing is first we have to initialize a tree. Remember, everything in our tree is a tree. So we initialize a new tree with that value. Another way you could do it is you could also pass a node here.
[00:03:01] So we can already pass our tree here. So up to you however you did it is fine. But if you pass a node here you would have to do this outside. So I like to encapsulate it here. So just give us the value, you don't need to worry about what the actual underlying data structure is whether or not it's a tree.
[00:03:24] We'll just initialize it for you less things to worry about. Like, if this wasn't a value, and it wasn't no, we might want to check first, that it's a tree so we don't run into issues later. So I like this API. It's a little bit simpler. And then let's talk about this next line.
[00:03:44] So when we create our tree, now we need to add it to the children of the tree. So let's try that out. So we have myTree, right? MyTree.insertChild.
>> Bianca Gandolfo: Right? Let's say two.
>> Bianca Gandolfo: Okay? So let's let's trace through this, so we have the value two, so we create a new Tree with the value two.
[00:04:17] This is pseudo code, but you can imagine it has value and also empty children. Then, we need to push it to this.children. So, this refers to the tree that is being called on. Right, so our first Tree, let's call this myTree1. Okay? And this will be Tree2. So this is my Tree1, right?
[00:04:45] And this dot children is here. Does that make sense? Any questions about that? Sunny did you have a question?
>> Speaker 3: Yes, it’s generally in terms of tree. Shouldn’t the trees not be unique, is there any property like that on trees?
>> Bianca Gandolfo: Shouldn’t they not be unique? It doesn’t have to be unique.
[00:05:09] There are many flavors of trees. And there are some like the binary search tree for example where having duplicates doesn't serve it. But there's no hard and fast rule that all nodes in a tree must be unique.
>> Speaker 3: And when we're inserting the child here. Do we need to do any kind of check where it is going?
[00:05:31] Or do we have just put it into the children.
>> Bianca Gandolfo: Yeah that's a great question. And I like this because it's saying what else can we be doing here that's different that we're not doing. So, for the insertion.
>> Bianca Gandolfo: For this case it doesn't really matter. If we were gonna implement a binary tree, which is a tree which has 2 nodes, we might wanna check if there's already two.
[00:05:57] Cuz we can't add another one, right? But this is just a general tree, we do what we want, and it doesn't really matter. But we do wanna make sure that you're inserting it into the right parent node. So that's why this is important, that you're holding reference to the right node that you want to insert to.
>> Speaker 3: There's one more thing.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: So going by this thing, no matter how many we insert, it will all go in one level of the tree, right?
>> Bianca Gandolfo: Yeah.
>> Speaker 3: Height will be just one, there'll be one paranode, and one all childrens. They won't be children of children, correct?
>> Bianca Gandolfo: You can. So how we would do that is we would say, const myTree2 = this because we we're returning that tree, remember? So now if we wanted to here let's put our reference to 2 here, maybe it's useful to do this.
>> Bianca Gandolfo: Okay, so.
>> Bianca Gandolfo: When we're console logging it's gonna log this hypothetically.
[00:07:12] And now we have reference to this child, right? It's an object with a value to an empty child array. And so let's just draw that out to have for our reference.
>> Bianca Gandolfo: Right.
>> Bianca Gandolfo: I don't know.
>> Bianca Gandolfo: Okay. So, now if we wanted to add a child to the third level, right?
[00:07:47] So we have the parent, we have the child and then the child's child, is that a great grandchild, is that how that works? No, that's just a grandchild. So if we wanted to add a parent, child, grandchild, yeah. Which is not an official tree term, just so you know, I'm just playing.
[00:08:06] What I encourage you to do in your interviews is just be lighthearted. Bring that side of yourself, at least I do, it's working out so far. Okay, so, if you wanna insert 3, right? So myTree2, let's jump in here, our value is 2. We're gonna make a new, insertChild value 3 here, value is 3.
[00:08:36] We're gonna create a new Tree with that value of 3. And then we're gonna push it to this.children. So this is a reference to myTree2, right? Which is this one, which is messed in here actually but it looks like this. But we're gonna push three, and then you can imagine that this is like another level