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?
Stack Solution from Leetcode:
class Solution:
def maxDepth_stack(self, root: BinaryTreeNode) -> Union[int, Literal[0]]:
if not root:
return 0
stack = [(1, root)] # The stack holds tuples of a node and its depth
max_depth = 0
while stack:
depth, node = stack.pop()
if node: # If the node is not None
# Update max_depth if current depth is greater
max_depth = max(max_depth, depth)
# Add the left child and its depth to the stack
stack.append((depth + 1, node.left))
# Add the right child and its depth to the stack
stack.append((depth + 1, node.right))
return max_depth
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 true. What you described earlier as what you expected, is closer to the truth.
Including the right child on the stack before visiting the left child could be one possible approach if you would implement the algorithm without recursion, using an explicit stack instead. But it is not how the recursive algorithm works.
Each execution context of a function creates a stackframe. You could imagine the stack frames as boxes, where each new box is placed on top of a previous box (stacking them). Names like root have a scope and lifetime that is limited to the "box" they are defined in.
In the following visualisation, execution goes from top to bottom, and smaller boxes are placed on top of larger boxes, so it is like looking at the stack from "above":
┌─maxDepth─────────────────────────────────┐
│ root is TreeNode(1) │
│ ┌─dfs_postorder(root)──────────────────┐ │
│ │ node is TreeNode(1) │ │
│ │ ┌─dfs_postorder(node.left)─────────┐ │ │
│ │ │ node is TreeNode(2) │ │ │
│ │ │ ┌─dfs_postorder(node.left)─────┐ │ │ │
│ │ │ │ node is TreeNode(4) │ │ │ │
│ │ │ │ ┌─dfs_postorder(node.left)─┐ │ │ │ │
│ │ │ │ │ node is None │ │ │ │ │
│ │ │ │ │ return 0 │ │ │ │ │
│ │ │ │ └──────────────────────────┘ │ │ │ │
│ │ │ │ ┌─dfs_postorder(node.right)┐ │ │ │ │
│ │ │ │ │ node is None │ │ │ │ │
│ │ │ │ │ return 0 │ │ │ │ │
│ │ │ │ └──────────────────────────┘ │ │ │ │
│ │ │ │ return max(0, 0) + 1 # 1 │ │ │ │
│ │ │ └──────────────────────────────┘ │ │ │
│ │ │ ┌─dfs_postorder(node.right)────┐ │ │ │
│ │ │ │ node is TreeNode(5) │ │ │ │
│ │ │ │ ┌─dfs_postorder(node.left)─┐ │ │ │ │
│ │ │ │ │ node is None │ │ │ │ │
│ │ │ │ │ return 0 │ │ │ │ │
│ │ │ │ └──────────────────────────┘ │ │ │ │
│ │ │ │ ┌─dfs_postorder(node.right)┐ │ │ │ │
│ │ │ │ │ node is None │ │ │ │ │
│ │ │ │ │ return 0 │ │ │ │ │
│ │ │ │ └──────────────────────────┘ │ │ │ │
│ │ │ │ return max(0, 0) + 1 # 1 │ │ │ │
│ │ │ └──────────────────────────────┘ │ │ │
│ │ │ return max(1, 1) + 1 # 2 │ │ │
│ │ └──────────────────────────────────┘ │ │
│ │ ┌─dfs_postorder(node.right)────────┐ │ │
│ │ │ node is TreeNode(3) │ │ │
│ │ │ ┌─dfs_postorder(node.left)─────┐ │ │ │
│ │ │ │ node is None │ │ │ │
│ │ │ │ return 0 │ │ │ │
│ │ │ └──────────────────────────────┘ │ │ │
│ │ │ ┌─dfs_postorder(node.right)────┐ │ │ │
│ │ │ │ node is None │ │ │ │
│ │ │ │ return 0 │ │ │ │
│ │ │ └──────────────────────────────┘ │ │ │
│ │ │ return max(0, 0) + 1 # 1 │ │ │
│ │ └──────────────────────────────────┘ │ │
│ │ return max(2, 1) + 1 # 3 │ │
│ └──────────────────────────────────────┘ │
│ return 3 │
└──────────────────────────────────────────┘
What is not shown here is the return address, which is also part of a stack frame: when an inner function call returns, the calling function context (preserved in a stack frame) has a trace of where to resume its execution.
When this recursion is "emulated" with an explicit stack and no recursive calls, it is not uncommon to replace this idea of a "return address" with the "next task to do", which is visiting the right child. So that is where the idea comes from to first push the right child (as a deferred task) and then the left child (as the immediate task).