Tree Methods Time Complexity

[00:00:00]
>> Bianca Gandolfo: Let's talk about time complexity super quick, insert.
>> Bianca Gandolfo: You guys remember how you implemented your insert?
>> Bianca Gandolfo: What do you think, do you have it open? You can look at the solutions, they're there.
>> Bianca Gandolfo: Wild guess? Someone who's quiet. How about, I feel like this area, you guys are really either focused or really not focused.

[00:00:34]
Just take a stab, what do you think? We need to add a node into our tree.
>> Speaker 2: If we're adding a node to an array that contains children, it'd be in a constant time. We're just adding it to the end.
>> Bianca Gandolfo: Mm-hm, yeah, if you add it to the end, for sure.

[00:00:50]
If you have reference to that node, right? So if we wanted to give 2 a child, 2 has an array of children that are empty
>> Bianca Gandolfo: And it would just be like, children.push, right, easy. If we don't have a reference to 2,
>> Bianca Gandolfo: How does that change things?

[00:01:18]
>> Speaker 2: We'll have to traverse to it.
>> Bianca Gandolfo: Yeah.
>> Speaker 3: So it's at least linear. For some reason, I wanna say log, but I don't know why.
>> Bianca Gandolfo: So-
>> Speaker 3: You don't have to traverse all the trees, so it's not gonna just necessarily go into at least linear.
>> Bianca Gandolfo: Right, but we have to think worst case scenario.

[00:01:38]
>> Speaker 3: Yeah.
>> Bianca Gandolfo: We have to be like, okay, what if it's in the farthest reaches of our tree, then we'd have to say linear, yeah. So it's linear if you had to look for it, right? Cuz traversing is linear.
>> Bianca Gandolfo: Counting the recommendations?
>> Speaker 3: You'd have to touch everything again.

[00:02:01]
>> Bianca Gandolfo: Yeah, linear.