We need to traverse a binary tree in preorder and return the node values as a list. Preorder traversal follows a specific visitation order: process the current node first, then recursively traverse the left subtree, then recursively traverse the right subtree. The name "preorder" comes from the fact that the node is processed before its children.

This is one of the three fundamental depth-first tree traversal patterns (preorder, inorder, postorder). While the recursive solution is straightforward, the real learning value here is understanding how to convert recursion into an iterative approach using an explicit stack, and then going further with Morris traversal to eliminate even the stack.

The key observation is that recursion uses the call stack implicitly. If we want to avoid recursion, we need to manage that stack ourselves. And if we want O(1) space, we need a clever trick with temporary thread links.

Key Constraints:

Intuition

The recursive approach is the most natural way to think about preorder traversal. The definition itself is recursive: visit the current node, then preorder-traverse the left subtree, then preorder-traverse the right subtree. Translating that directly into code gives us a clean three-line recursive function.

This is usually where you'd start in an interview. It shows you understand the traversal order, and it's hard to get wrong. The recursion handles all the bookkeeping of which nodes to visit next by using the call stack.

Algorithm

Example Walkthrough

Code

The recursive approach uses the call stack implicitly. For deeply skewed trees, this can risk a stack overflow.

What if we managed the stack explicitly so we could control the memory?

Intuition

The recursive solution uses the call stack to remember where to go next. We can make this explicit by using our own stack data structure. The insight is that preorder traversal processes the current node, then needs to visit the left subtree before the right subtree. Since a stack is LIFO (last in, first out), we push the right child first, then the left child. That way, the left child sits on top and gets processed first.

This is a classic interview technique: converting recursion to iteration using an explicit stack. It's worth knowing because interviewers often ask for the iterative version as a follow-up.

Algorithm

Example Walkthrough

Code

Both the recursive and iterative approaches use O(h) extra space. Can we do better?

What if we could temporarily modify the tree structure to navigate back to ancestors without any extra space?

Intuition

Morris traversal is a clever technique that achieves O(1) extra space by temporarily modifying the tree. The core idea is: when we're about to explore a node's left subtree, we create a temporary link (a "thread") from the rightmost node in that left subtree back to the current node. This way, after finishing the left subtree, we can follow this thread back to the current node and continue with the right subtree, no stack needed.

For preorder specifically, we add the current node to the result as soon as we first encounter it (before going left). The thread just tells us how to get back.

Here's how to think about it: in a regular preorder traversal, after you finish the entire left subtree of a node, you need to somehow return to that node to visit its right subtree. Normally the stack handles this. Morris traversal instead says, "Before I go left, let me set up a breadcrumb trail so I can find my way back."

Algorithm

Example Walkthrough

Code