Tree remove Solution

[00:00:00]
>> Bianca: Let's talk about removeChild. DId anyone get to it? How did you remove it?
>> Speaker 2: I just rendered the children and checked the children's values, whatever value we're passing.
>> Bianca: And you just removed it, cool. So deleting trees can be really interesting, because what if you delete a node in the middle?

[00:00:25]
So what if you have a child that has children like this? So what if we wanted to delete 7, right? How would we want to handle that? So, in this case, if we deleted 7, then we would delete the entire sub-tree. Which is fine, we just need to know that's what we're doing.

[00:00:48]
Other ways that we could do it is we could take the 7, replace it with something else. There might be rules for your tree. Right now, our trees are free-spirited trees, they can do whatever they want. But a lot of trees have rules and structures that they need to follow and so the exit policy matters.

[00:01:07]
And you might imagine, deleting entire subtrees might be really bad for some things, but it could be really good for other things. React will just delete the whole subtree and re-render the DOM. And it's an optimization because you'll see that the deleting nodes is a little quirky. It's a little weird.

[00:01:29]
There are a lot of edge cases. So I'm just gonna leave it question mark for you just to start thinking about it. And we'll talk about removing nodes from trees. Actually, it's the very last thing that we do. We're gonna talk about deleting from a binary search tree.

[00:01:45]
But just know, you can set the children to that space, you can splice it out, however you want to delete something from an array. All right, I set it to undefined which is kind of weird, but you could, you could splice it, you can create a new array without it.

[00:02:02]
Which is kinda like splicing it, but it's for the immutable people, if you're into that. Yeah, cool. So inserting into a tree is constant time, why?
>> Speaker 2: We're just inserting the new node at the end of the array?
>> Bianca: Yeah, so thinking back to our linear data structure when we talked about pushing values to the end of an array constant.

[00:02:38]
And there's nothing else in here that is really noteworthy of an activity. So let's talk about what makes an activity noteworthy for time complexity analysis. It's anything like if you see something with loops, that's important. Any array, array methods can be tricky, all these native methods under the hood might secretly have a loop.

[00:03:02]
Recursion is another one. Instantiating a class, no big deal. We're just creating an object that's going to be negligible, returning negligible. Yeah, so we'll go through and we'll keep talking about what we should be looking out for. Any questions? All right.
>> Speaker 3: How do we know what is on the left and the right of the tree?

[00:03:40]
>> Speaker 3: Or how do we know what child is on the left or the right?
>> Bianca: I guess my first question is why does it matter if it's the left or the right, but I mean, the concept of having a left or a right comes from a binary tree and this is just a regular tree, so it doesn't really matter for this.

[00:04:04]
But if you wanted to do a left or right, we gonna talk about that next. Because our chat bot is really a binary tree because we have yes and no, right? Instead of left or right, we have yes or no. And then we're gonna get really serious about left and right with our binary search tree, which is kind of an evolution of that.

[00:04:24]
>> Speaker 4: So you're saying to remove that tree is constant or to move a node is constant? Is that what you're saying?
>> Bianca: It depends on how you do it.
>> Speaker 4: That's what I was wondeing.
>> Bianca: Yeah. So if you're just setting 7 here to null, that's constant. You're just removing a reference.

[00:04:49]
You're just basically setting this null. So this is just this 2 is now pointing null.
>> Speaker 4: But don't you have to search for it?
>> Bianca: In these cases, we have a reference to the child. So this is like a removeChild on the tree, it's gonna remove a child with that value.

[00:05:10]
Does that make sense? Just like the insert, we have a reference. But that's a good point, right? If we have to start from the root note it reverse to the tree, which we will do later, it gets different, the time complexity is gonna evolve. And so this is why you can't just be like, inserting the tree is this time complexity, right?

[00:05:31]
It actually really matters how you're inserting it and the kind of tree that you're working with, so we just need to be aware of all the factors.
>> Speaker 2: In this example, when you're saying removeChild(value), that value is actually a no or it's not the value we had an insertChild.

[00:05:46]
So how I looked at that was you're asking, like, give me root of the child that has this value as its value. Meaning, I have to look at all the children, I'm not just searching for the value, I'm searching for the thing having the value.
>> Bianca: Yes.
>> Speaker 2: So the two arguments there, the methods are congruent, so the same kind of thing you're passing in.

[00:06:10]
So I'm not passing in the node that contains 7, I'm passing in 7.
>> Bianca: Yeah, so you would loop for the children array and find it. But you wouldn't be looping through that and the children's children, like it's not-
>> Speaker 2: Not transversing the whole tree.
>> Bianca: Yeah, exactly.

[00:06:24]
>> Speaker 2: So it's not linear, then?
>> Bianca: Mm-hm.
>> Speaker 2: Okay, so it's not constant?
>> Bianca: Yes. Did I say it was constant?
>> Speaker 2: Yeah, I thought it was, okay, yeah, okay.
>> Bianca: So the setting it is constant.
>> Speaker 2: Setting it, okay, I see what you're saying.
>> Bianca: But to get to it is gonna be linear for sure.

[00:06:42]
>> Speaker 2: Okay.
>> Bianca: Yeah, cool, sorry if I misspoke.