Searching a tree - Python Tutorial

- [Instructor] In this section, we're going to do something so fundamental to binary search trees that it's literally in the name. We are going to binary them. No, I'm kidding, we're going to search them. We will search the binary search tree. So remember this fundamental property of the binary search tree. The small values always go to the left and the large values always go to the right. So if I'm starting at the root and I want to find 27, what do I do first? Start here and say, is 27 less than or greater than 50? So obviously 27 is less than 50, so going to 25. And I say, is 27 less than or greater than 25? It's greater than, so awesome, I found the 27. So let's write this up in code using the node class from the last section. Let's make a function in the node class called search. And this is going to take in a target, which is the data that we're looking for in the tree. And the first thing we're going to do is check the case where this current node. Self matches the target that we're searching for. So if self.data equals target, let's print "found it" or something like that, and then return self. So returning the node that we found in the tree. Otherwise, if we don't match it, we need to keep looking. So if we have a left node, if our current self has a left node, if self.left, then we'll need to check to see if the target is on the left side of the tree. That is, the target is less than the current data. So, and self.data is greater than target, we are going to recursively keep searching the tree. So let's return self.left.search for the same target. And then we do the same thing on the right side. Check if the right exists, if self self.right and self.data is less than target. Return self.right.search target. Now, there's a case that's missing here or at least not explicitly written. So what happens when the data we're searching for isn't in the tree? In that case, it'll fall through to the end here. It won't find a viable left or right node. It can't keep going, so it's just going to return none. Remember in Python, there's always an invisible return none at the end. So let's just add a print statement, letting us know that it didn't find anything. There we go. So let's try this out with the tree that we created in the last section. Let's say found is going to be equal to tree.root.search, and let's look for node 10,000. Okay, so found is going to actually just be that node object there. So let's print found.data. Oh, sorry, that's my tree. Great, found it. And it returns that note with the value of 10,000. Note that we can also take advantage of our tree class here as a rapper and not a convenience function, search. And that's going to take self and then just search the root node. Return self.root.search for a target. Target, target. And by adding these functions into this tree rapper, it just kind of creates a nice way of accessing it. So instead of calling my tree.root.search, I can just call my tree.search. Found it, 10,000. Alright, great.