__slots__ is advanced and you probably shouldn’t bother with it unless you really need it. It is used to reduce memory consumption for objects by avoiding creating a
__dict__ for storing attributes.
By default, instances have an internal dict for storing arbitrary attributes. Instead, we can declare up front what attributes are needed, and memory will be reserved for them directly instead of inside the internal dict.
So you could remove the
__slots__ line from the Node class, and the only difference would be that the individual nodes would use a little more memory, and you could assign arbitrary attributes to them.
Names that start and end with double underscores
__ are called dunder (Double UNDERscore) names, or just dunders. Dunders are reserved for special use by the Python interpreter.
Names that start with a single underscore are considered “private”. By convention, code outside of the Node class is supposed to not touch the Node private attributes.
Nodes that start with two underscores (but not end with them) are also considered private, but more so. The interpreter takes the name and automatically mangles it by inserting the name of the class, so to help avoid name clashes with subclasses.
All of this is considered moderately advanced so don’t worry about it if you find it hard to understand.
(But feel free to ask more questions if you wish.)
I think you could re-write the two classes in a simpler fashion without losing any functionality:
def __init__ (self, item, left=None, right=None):
self.item = item
self.left = left
self.right = right
def __init__ (self, root=None):
self.root = root
def search(self, key):
# Search the tree for the node containing the key.
return self._search(self.root, key)
def _search(self, node, key):
if node is None: # empty tree does not contain the key
elif key == node.item:
# Found it!
elif (key < node.item):
# Search the left subtree.
return self._search(node.left, key)
# Search the right subtree.
return self._search(node.right, key)
I also changed the name “get” to search.
I removed the underscores from most of the names because this is a learning exercise and they really aren’t needed. Feel free to put them back if you wish.
The search() method (originally called “get”) takes one argument, the key to search for, and returns the node containing that key.
If order to find that node, it calls a second method
_search. It has a leading underscore to tell you that only the BinaryTree class should use that method. This method does the work of actually inspecting each node and deciding whether or not it matches the key we are looking for.
That needs to be a second method because, unlike the search() method, it needs two arguments: the key to search for, and the current node where we are up to in the search.