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.

First Few Test Cases:

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:

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!