BST, Recursion
Decide if you should head left or right from a node by comparing the node data and the data you want to add. If the left or right slot is open, you can add the new node there. If it isn’t, you can call this method recursively on the left/right node, looking to add the new value to left or right of that.
class Node(object): # ...
def insert(self, new_data):
"""Insert new node with `new_data` to BST tree rooted here."""
# START SOLUTION
if new_data >= self.data:
if self.right is None:
self.right = Node(new_data)
else:
self.right.insert(new_data)
else:
if self.left is None:
self.left = Node(new_data)
else:
self.left.insert(new_data)