Recursion

Iterative Tree DFS

Lesson

It turns out you can implement any recursion using while loops, instead of using a recursive function. This is called "iterative" code. We'll go over how to write all the DFS traversals (preorder, inorder, postorder) iteratively in this lesson and the following problems.

Iterative Preorder Traversal

Problem: Write code for a preorder traversal, but do it without using a function that calls itself. Use a while loop instead.

First Few Test Cases:

Here's the recursive code we want to make iterative:

To convert this recursive code to "iterative" code, you need to implement your own version of a Call Stack rather than using the computer's Call Stack. All this means is you should keep a stack of all the nodes you want to call visitAll on. Just keep removing nodes from the stack and operating on them as visitAll would.

Below, stack contains all the nodes we want to call visitAll on.

Notice that we add to the stack in reverse order so that node.left gets operated on before node.right. This is because the last thing added will be on the top of the stack.

Time Complexity: $O(n)$ . We do an O(1) operation per node, and there are n nodes.

Space Complexity: $O(n)$ . The stack gets as tall as the Call Stack would have gotten, because it's literally our own version of the Call Stack. For a very skewed tree, the height is O(n), so that's the space complexity.

Mark as Completed:

Submits:

preorderTraversal

Imports:

TreeNode

Test your code to get an output here!

preorderTraversal(

)

Test your code to get an output here!