Why does this code for a recursive preorder traversal on a binary tree work? Shouldn't it get stuck at the first recursive call?

Question

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        out = []
        def preorder(node):
            if not node: return

            out.append(node.val)
            preorder(node.left)
            preorder(node.right)

            return

        preorder(root)
        return out

This code is the code I saw in the solutions, it almost makes sense to me other than the recursive function calls. I understand it is return the correct solution, but I'm unsure why it works.

I have ran the code myself and it 100% works and passes all the LeetCode test cases. The part I'm Struggling to understand is the 2nd recursive function call:

            out.append(node.val)
            preorder(node.left)
            preorder(node.right) # This one here

What I'm struggling to understand is why/how the code ever hits this point. To me, the code should never hit this point, as there is a recursive function call prior that has no condition to be met. Why isn't the code just continuously attempting to run the line before? (preorder(node.left)).

The only explanation I can think of, is that because when we are on the final node that would be applicable to the first recursive call, we would then be passing in None/Null. Does python know that this would result in nothing happening and skip to the next line? How is it actually possible for preorder(node.right) to be executed when preorder(node.left) exists above it, and requires no conditionals to be met to execute?

Answer 1

The recursion stops at this line:

    if not node: return

So, when there are no more left nodes, this happens:

        out.append(node.val)
        preorder(node.left)  # Return None
        preorder(node.right) # Starting going to the right

You might imagine that as the function goes all the left nodes are appended while the right nodes wait until there are no more left nodes.

A good exercise is to run this code in debug mode

ps: This process is known as Depth-First Search (DFS), where it goes as deep as it can into the tree before backtracking and going to the right node.