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?