Iteration

Converting Recursion to Iterative

Lesson

Recursive functions probably felt strange to you at first, and you might wonder if it's possible to convert a recursive function into while-loops, called "iterative" code. It is indeed possible. This is never necessary, but in theory it can be a little faster and use less memory.

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.

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!