Preorder Traversal (Iterative)

1. One-Liner

Iterative preorder visits root → left → right using a stack, pushing children so left is processed before right.

2. The Problem It Solves

You need a DFS order that lists the root before subtrees (copying trees, prefix expressions, serialization) without recursion—useful when call depth is limited or you want an explicit frontier.

3. The Core Idea

Pop the current node, record its value, then push right then left so the stack yields left on top next. This preserves preorder while using LIFO instead of the function-call stack.

4. How It Works (Step-by-Step)

Step	Action
1	Push root on stack (if not null).
2	While stack not empty: pop node, append its value.
3	Push right child, then left child (if exist).
4	Next pop visits left subtree first—preorder.
5	Stop when stack empty.

5. Dry Run Example

Tree: root 1, children 2 (L), 3 (R).

Pop	Stack after push	Output
1	[3,2]	[1]
2	[3]	[1,2]
3	[]	[1,2,3]

6. Key Properties

Property	Detail
Order	Root before its subtrees
Space	O(h) stack typical
Mirror	Swap push order for “root-right-left”

7. Where It Is Used

Area	Use
Serialization	Save tree to file stream
Cloning	Create nodes in parent-first order
Parsing	Expression tree prefix evaluation

8. Interview Tips

Right before left on stack is the classic gotcha. Contrast with inorder (no simple single-stack pop order). Know Morris preorder as O(1) space follow-up.

9. Comparison with Other Algorithms

Variant	Order	Typical stack
Preorder iter	Root-L-R	Node stack
Inorder iter	L-Root-R	Descend-left style
BFS level	Level-wise	Queue

10. Complexity


--	--
Time	O(n)
Space	O(h) worst O(n)

Implementation Example (PYTHON)

def preorder_iterative(root):
    if not root:
        return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out