Iteration

Converting Recursion to Iterative

Lesson

Every problem can be solved using recursion.

Every problem can also be solved without using recursion, called "iterative" code.

You can switch between the two. In this section we practice going from recursive code to iterative code.

To turn any recursive code into iterative code, you need to keep track of your recursive function's calls in your own stack, instead of having the computer do it for you in the built-in Call Stack.

You usually make your recursion into iterative code when: 1. your Call Stack gets taller than Python's limit (1000), or 2. you want to return early. This is never necessary, but in theory it can do slightly fewer operations and use less memory.

Iterative Number of Tree Nodes

Problem: Here's the very first recursion we wrote. Try converting this recursive code to iterative code. If you get stuck, read the solution below.

def numNodes(root):
    if root is None:
        return 0
    nL = numNodes(root.left)
    nR = numNodes(root.right)
    return 1 + nL + nR

First Few Test Cases:

numNodes(TreeNode.of([1]))
# 1

numNodes(TreeNode.of([1, 2]))
# 2

numNodes(TreeNode.of([1, 2, 3]))
# 3

This problem might seem difficult because you need to make 2 different recursive calls to compute $\tt nL$ and $\tt nR$ before returning from the function.

The trick to doing this is to visit each node twice. The first time you see a node, you should call the function on its left and right children root.left and root.right. The second time you see a node, the numNodes for the children have already been computed. This means you can use them to compute the $\texttt{numNodes}$ of the current node.

Here's the full iterative code:

def numNodes(root):

    stack = [(root, True)] # your own Call Stack
    numNodes = {} # node -> numNodes(node)

    while stack:
        # pop the top node from the stack and compute numNodes(node) on it
        node, isFirstCall = stack.pop()

        # base case
        if node is None:
            numNodes[node] = 0
            continue
            
        # if this is the first time we've seen this node,
        # compute numNodes on the children and then come back
        if isFirstCall:
            stack.append((node, False))
            stack.append((node.right, True))
            stack.append((node.left, True))

        # recursion
        else:
            nL = numNodes[node.left]
            nR = numNodes[node.right]
            numNodes[node] = 1 + nL + nR

    return numNodes[root]

Time Complexity $O(n)$

Space Complexity $O(n)$ . The stack grows in the same exact way as the recursive solution, so it has the same space complexity.

Mark as Completed:

Submits:

numNodes

Imports:

TreeNode

Test your code to get an output here!

numNodes(

)

Test your code to get an output here!