Tree and Graph Data Structures

insert Node

Bianca Gandolfo

Thumbtack

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

The "insert Node" 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 analyzes each step in the process of inserting a node into a preexisting binary search tree.

Preview
Close

Transcript from the "insert Node" Lesson

[00:00:00]
>> Bianca Gandolfo: So let's just talk about insertion really quickly. So, we have a root node here of 3, we wanna insert this value 20. At every step, we need to do a comparison, right? We say, is this greater than or less than? Let's take a peek. So, I got 3, greater than or less than?

[00:00:20]
Greater than, so we go right. 15, greater than or less than? So we go, it's greater than, right, we go right. 20, greater than or less than? It's less than, right, or 26, it's less than, so we go left. 21, greater than or less than?
>> Audience: Less.
>> Bianca Gandolfo: Greater than or less than?

[00:00:45]
>> Audience: Greater than.
>> Bianca Gandolfo: Greater.
>> Audience: Yep.
>> Bianca Gandolfo: And that's how we find it's spot. So we when we insert a node, we have to go through and compare until we find an open spot where it meets the criteria, mm-hm?
>> Audience: Why do we put 20 as a child to 19 instead of put it between 19 and 21 or 15 and 26?

[00:01:12]
>> Bianca Gandolfo: So at each point, you have to compare. So at 15, it's greater, so it has to go right. At 26, it's less than, so it has to go left. 21, it's less than, so it has to go left. 19, it's greater than, and there's a spot. It has to have a spot, cuz it either has to go to a left or right.

[00:01:35]
>> Bianca Gandolfo: Mm-hm, yeah.
>> Audience: And it can only have two spots.
>> Bianca Gandolfo: Yeah, so if it was 22-
>> Audience: But you were thinking inserting, I mean you could've put it between.
>> Bianca Gandolfo: Then you'd have to rebalance the two.
>> Audience: Okay, I see.
>> Bianca Gandolfo: For sure, cool.