[Python] What form of recursion is occurring in the "insert "and "list_all" methods of this...

I am struggling to understand the recursion going on in the insert, _insert_recursive and _inroder_traversal methods. For context, I know recursion and the concept is not strange to me, I struggle to visualize it in the stated methods. They are all methods of the same class UserDatabase.

class TreeNode:
def __init__(self, key, user):
self.key = key # Username is used as key for sorting
self.user = user # stores User object
self.left = None
self.right = None

# User Database implemented using BST
class UserDatabase:
def __init__(self):
self.root = None # BST root (first user)

# inserts a new user into the BST
def insert(self, user):
"""Insert user into BST based on username."""
if self.root is None:
self.root = TreeNode(user.username, user)
else:
self._insert_recursive(self.root, user)

# Finds the correct position for the new user in the BST and inserts it arguments are for comparison
def _insert_recursive(self, node, user):
if user.username < node.key:
if node.left is None:
node.left = TreeNode(user.username, user)
else:
self._insert_recursive(node.left, user)
else:
if node.right is None:
node.right = TreeNode(user.username, user)
else:
self._insert_recursive(node.right, user)



def list_all(self):
"""Return all users in sorted order using in-order traversal."""
users = []
self._inorder_traversal(self.root, users)
return users

def _inorder_traversal(self, node, users):
"""Recursive in-order traversal to get sorted list of users."""
if node is not None:
self._inorder_traversal(node.left, users)
users.append(node.user) # Append user object
self._inorder_traversal(node.right, users)


For the list_all(self), I expected no output to be shown since there is no return statement in the _inorder_traversal(self, users) method, for the insert (self, user), the whole method's operation is difficult to understand and I need another perspective on its operation, or even an analogy. I hope this make makes the problem clearer , thanks

Continue reading...