From the course: Python Data Structures: Trees

Adding nodes - Python Tutorial

From the course: Python Data Structures: Trees

Start my 1-month free trial

Adding nodes

- [Instructor] Up until this point, every interaction we've had with the tree has been to read it without any modification. But in this chapter, we'll start learning a few of the basic methods of tree modification and actually start changing these trees. The most obvious modification of course is to add data to the tree. Fortunately, this is also one of the easiest. We're going to write a function very similar to the search function from chapter one, section two. In fact, the code is almost completely identical apart from what happens when we find the node and what happens when we don't find the node. So this is the original search function, and I'm literally just going to copy paste it. Change the name to add and change the variable target to data. This isn't obviously changing target to data isn't a functional change, but this is no longer a target we're searching for, it's data that we're adding. And so I think it makes sense to change the variable name there. Just change it in a few places there. If the date data is equal to the data that we found in the current node, there's nothing to do. Remember trees can't have duplicates, so let's just return and do nothing. And here we're basically continuing our tree search, if there's a left child, and the data we're searching for is smaller than the current data, we're going to keep going and we're going to recurse down now looking to add that data, same with the right side. But there's still a case we're missing and that's the part where we actually add the data. So if the data is less than the current nodes data and there's no left child, what we want to do is actually just add the data at this point. And we can rewrite this a little bit to make this more efficient. So, if data is less than self.data if self.left is None, here's where we want to add the data self.left = Node. We'll make a new node with that data. So if there's no left child, the data should go there and we're setting the left child equal to the data. And then here's where we recurse else: self.left, does exist. Self.left.add data. Now, I'm just going to copy and paste this and switch it around for the right side. So, change that to a greater than right, right, right. Trees are wonderfully somatic. So, now we have our add function and let's actually test it out and let's add a wrapper here too as always def add self, data. Self.root.add data. Great. And I happen to have a tree hanging around here. Let's add tree.add insert a 10. Great, get out of the 10 and we can try it with a tree.add. I don't know, 76. Cool. And what if we do tree.add one that's already in there, like 75. Takes no action. Perfect. So now you know how to add data to trees.

Contents