Tree and Graph Data Structures

Tree Methods Time Complexity

Tree and Graph Data Structures

Check out a free preview of the full Tree and Graph Data Structures course

The "Tree Methods Time Complexity" Lesson is part of the full, Tree and Graph Data Structures course featured in this preview video. Here's what you'd learn in this lesson:

Bianca outlines the time complexity of the four methods for trees that were covered in previous lessons.


Transcript from the "Tree Methods Time Complexity" Lesson

>> 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.

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.

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?

>> 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.

>> 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.

>> Bianca Gandolfo: Yeah, linear.

Learn Straight from the Experts Who Shape the Modern Web

  • In-depth Courses
  • Industry Leading Experts
  • Learning Paths
  • Live Interactive Workshops
Get Unlimited Access Now