Introduction

Pre-order traversal visits node, then left subtree, then right subtree. Most examples use recursion or an explicit stack, but both consume extra memory proportional to tree height. Stackless traversal techniques reduce auxiliary space and are useful when memory constraints or deep trees make recursive traversal risky.

Core Sections

Pre-order traversal goal and baseline behavior

In pre-order, every node must be emitted before its descendants. For a tree with root value 1, left child 2, right child 3, and left-left child 4, output should be 1 2 4 3.

A stackless approach must preserve this order without recursion and without a separate stack structure.

Morris-style pre-order traversal

The most common stackless approach is Morris traversal. It temporarily rewires right pointers to create return links, then restores the tree structure.

1class Node:
2    def __init__(self, val, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7
8def morris_preorder(root):
9    result = []
10    cur = root
11
12    while cur:
13        if cur.left is None:
14            result.append(cur.val)
15            cur = cur.right
16        else:
17            pred = cur.left
18            while pred.right is not None and pred.right is not cur:
19                pred = pred.right
20
21            if pred.right is None:
22                result.append(cur.val)   # pre-order visit on first encounter
23                pred.right = cur         # temporary thread
24                cur = cur.left
25            else:
26                pred.right = None        # restore tree
27                cur = cur.right
28
29    return result

This algorithm runs in linear time and constant extra space, excluding output list.

Why Morris pre-order works

For each node with a left child, the algorithm finds the rightmost node in that left subtree. That node acts as predecessor. The predecessor right link is used as a temporary return edge to parent after left subtree exploration.

The key pre-order rule is satisfied by visiting node when thread is first created, before moving into left subtree.

Tree restoration guarantees

A frequent concern is whether Morris traversal leaves the tree mutated. Correct implementation always restores every temporary thread. To verify, run an in-order or pre-order traversal after Morris traversal and compare with expected structure.

Restoration bugs usually come from missing pred.right = None in second-visit branch.

Alternative stackless approach with parent pointers

If nodes contain parent references, traversal can be done without stack and without temporary rewiring.

1def preorder_with_parent(root):
2    result = []
3    cur = root
4    prev = None
5
6    while cur:
7        if prev is cur.parent if hasattr(cur, 'parent') else False:
8            result.append(cur.val)
9            nxt = cur.left or cur.right or cur.parent
10        elif prev is cur.left:
11            nxt = cur.right or cur.parent
12        else:
13            nxt = cur.parent
14
15        prev, cur = cur, nxt
16
17    return result

This avoids pointer rewiring but requires parent links in node model.

Complexity and performance notes

Morris traversal is linear time, but predecessor search does repeated pointer walking. In practice it is still efficient and memory-friendly. For performance-critical contexts, benchmark against iterative stack version because constant factors vary by tree shape.

Highly skewed trees reduce recursion safety benefits because recursive depth becomes large, making stackless methods more attractive.

Testing strategy

Test with:

• empty tree,
• single-node tree,
• full balanced tree,
• left-skewed and right-skewed trees,
• random trees compared against known recursive pre-order result.

Use property checks where possible: output length equals node count, and node values are visited exactly once.

When not to use Morris traversal

Avoid Morris traversal in concurrent structures where temporary pointer rewiring could violate thread-safety assumptions. Also avoid it when tree nodes are immutable by design.

In those cases, iterative traversal with explicit stack is safer and easier to reason about.

Common Pitfalls

• Visiting node in wrong branch and producing in-order-like output accidentally.
• Forgetting to remove temporary thread pointer and corrupting tree structure.
• Using Morris algorithm on immutable tree nodes.
• Comparing performance without considering tree shape and cache effects.
• Skipping edge-case tests for skewed trees and single-node trees.

Summary

• Stackless pre-order traversal can be achieved with Morris threading in constant extra space.
• Correct pre-order behavior depends on visiting node before descending left on first encounter.
• Temporary thread links must be restored to preserve original tree structure.
• Parent-pointer traversal is another stackless option when parent links exist.
• Validate implementation against recursive baseline on varied tree shapes.