Understanding the Internal Stack Frames in a Recursive Function Call

Question

I'm trying to understand how the system's call stack works internally when a recursive function is called. Specifically, I'm looking at a function that computes the maximum depth of a binary tree using a postorder traversal.

I do know there is a stack solution out there, but I would one that mimics the internal call as closely as possible.

Here's the tree I'm working with:

    1
   / \
  2   3
 / \
4   5

And here's the recursive function:

def maxDepth(root: Optional[TreeNode]) -> int:
    def dfs_postorder(node: TreeNode) -> Union[int, Literal[0]]:
        if not node:
            return 0

        left_depth = dfs_postorder(node.left)
        right_depth = dfs_postorder(node.right)
        return max(left_depth, right_depth) + 1

    return dfs_postorder(root)

When this function is run on the tree, it first calls itself on the root, then on the root's left child, then on the left child's left child, and so on, until it reaches a leaf. At each step, it adds a frame to the call stack.

However, I'm confused about when the right children get added to the stack. From my understanding of the code, it seems like the function would only start processing the right children after it has finished with all the left children.

For instance, after the first call to the function (with the root node 1), I would expect the next call to be with the left child (2), and the system's call stack to look like this:

[(1, "processed"), (2, "process")]

where process means the node's left and right are yet to be explored and processed means we explored its left and right and probably ready to be "popped" later.

However, I've been told that even at this early stage, the call stack would also include a frame for the right child (3), like this:

[(1, "processed"), (3, "process"), (2, "process")]

Why is this the case? How does the system's call stack actually work in this situation?

Answer 1

It might be helpful to think of call-stack frames as remembering "where to return to" when a function call returns. There are two recursive calls in your example (one for the left child, and one for the right), so there are two possibilities of where those calls should return to.

Let's label these two return points, A and B:

    left_depth = dfs_postorder(node.left)
A:
    right_depth = dfs_postorder(node.right)
B:
    return max(left_depth, right_depth) + 1

All the call-stack needs to do is remember whether or not it is returning to the code at A, or returning to the code at B.

---

While processing node 2, the stack looks something like the following. Here, the stack remembers that, when we return to node 1, the program should continue at point A in the code.

[(node: 1, continue_at: A), (node: 2, ...)]

Later, the program continues with node 1 at point A, causing it to start processing the right child, at which point the stack looks like this:

[(node: 1, continue_at: B), (node: 3, ...)]

---

Now, to address this point:

However, I've been told that even at this early stage, the call stack would also include a frame for the right child

This is not correct. The call-stack includes a frame that remembers it should continue at point A, but there is no explicit frame for the right child (yet). It just so happens that the next thing to occur at point A is a call that will begin processing the right child.