Binary Tree Preorder Traversal
Understanding the Problem
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.
Recursion uses the call stack implicitly. Avoiding recursion means managing that stack ourselves, and reaching O(1) space means replacing the stack with temporary links stored in the tree itself.
Key Constraints:
Number of nodes in range [0, 100]→ With at most 100 nodes, any approach works. The focus here is on understanding traversal techniques, not optimizing for large inputs.-100 <= Node.val <= 100→ Node values can be negative. This doesn't affect traversal logic.- The tree can be empty (0 nodes), so we need to handle the null root case.
Approach 1: Recursive DFS
Intuition
The definition of preorder traversal is itself recursive: visit the current node, then preorder-traverse the left subtree, then preorder-traverse the right subtree. Translating that definition directly into code gives a short recursive function. The call stack tracks where to resume after each recursive call returns, so the function needs no explicit bookkeeping of its own.
Algorithm
- If the root is null, return an empty list.
- Create an empty result list.
- Define a recursive helper function
preorder(node): - If
nodeis null, return. - Add
node.valto the result list. - Recurse on
node.left. - Recurse on
node.right. - Call
preorder(root)and return the result.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node in the tree exactly once, doing O(1) work per node.
- Space Complexity: O(h) where h is the height of the tree. The recursion stack holds at most h frames. In the worst case (skewed tree), h = n. For a balanced tree, h = log n.
The call stack has a fixed size limit, and a deeply skewed tree can overflow it. The next approach moves the stack into a data structure we allocate and control ourselves.
Approach 2: Iterative with Stack
Intuition
The recursive solution uses the call stack to remember where to resume after each subtree. An explicit stack of our own does the same job. Preorder processes the current node first, then the left subtree, then the right subtree. Because a stack is LIFO (last in, first out), pushing the right child before the left child leaves the left child on top: the left subtree is processed first while the right child waits on the stack, which produces the order node, left subtree, right subtree.
Algorithm
- If the root is null, return an empty list.
- Create an empty result list and a stack. Push the root onto the stack.
- While the stack is not empty:
- Pop a node from the stack.
- Add its value to the result list.
- If the node has a right child, push it onto the stack.
- If the node has a left child, push it onto the stack.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n). Each node is pushed onto the stack once and popped once, so we do O(1) work per node.
- Space Complexity: O(h) where h is the height of the tree. The stack holds at most h nodes at any time. In the worst case (skewed tree), this is O(n). For a balanced tree, it's O(log n).
Both the recursive and iterative approaches use O(h) extra space. Morris traversal removes the stack entirely by storing the return path inside the tree's own unused pointers.
Approach 3: Morris Traversal (Optimal Space)
Intuition
Morris traversal achieves O(1) extra space by temporarily modifying the tree. Before entering a node's left subtree, it creates a temporary link (a "thread") from the rightmost node of that left subtree back to the current node. After the left subtree finishes, the traversal follows the thread back to the current node and continues into the right subtree. The thread replaces the stack: the information about where to return is stored in the tree itself.
For preorder specifically, the current node is added to the result on the first encounter, before going left. On the second encounter, reached by following the thread, the thread is removed and nothing is added.
The thread is written into a pointer that is null by construction: the predecessor search follows right pointers until it reaches a node with no right child. Repurposing that null pointer as the thread back to the ancestor overwrites no information and allocates no extra memory. The tree is restored to its original shape before the traversal ends, because every thread created on a first visit is removed on the corresponding second visit.
A node is reached as current at most twice: once through normal traversal, and a second time only by following a thread, which exists only if the node has a left child. This bound on revisits is what keeps the total running time linear.
Algorithm
- Initialize
currentto the root and create an empty result list. - While
currentis not null: - If
currenthas no left child: addcurrent.valto the result, move tocurrent.right. - If
currenthas a left child: find the inorder predecessor (rightmost node in left subtree). - If predecessor's right is null (first visit): create thread, add
current.valto result, move left. - If predecessor's right is
current(second visit): remove thread, move right. - Return the result.
Example Walkthrough
Code
- Time Complexity: O(n). While finding the predecessor looks expensive, the total work across all predecessor searches is O(n) since each edge is traversed at most twice.
- Space Complexity: O(1). No stack or recursion is used. Only a constant number of pointers are needed.