DSA interview question

Iterative Preorder Traversal

Easy · Data structures · Topics: tree, stack

The problem

A code-analysis service walks huge abstract syntax trees, some thousands of levels deep, and recursion overflows the call stack. The traversal must be rewritten with an explicit stack. For preorder (node, left, right), pop a node, record it, then push its right child before its left child. The stack is last-in first-out, so the left subtree is processed first.

Example: [1, 2, 3, 4, 5, 6, 7] → [1, 2, 4, 5, 3, 6, 7].

Function signature

vector<int> preorderIterative(TreeNode* root);

Test cases

Input (level order)	Output	Explanation
`[1, null, 2, 3]`	`[1, 2, 3]`
`[1, 2, 3, 4, 5, 6, 7]`	`[1, 2, 4, 5, 3, 6, 7]`
`[1, 2, null, 3]`	`[1, 2, 3]`	A left chain
`[1, null, 2, null, 3]`	`[1, 2, 3]`	A right chain
`[]`	`[]`

(Confirm: no recursion; the output matches recursive preorder.)

How interviewers phrase it

"Return the preorder traversal of a binary tree iteratively" (LeetCode 144's follow-up).

Clarifying questions to ask

May I use an explicit stack? (Yes; Morris is the O(1)-space alternative.)
How deep can the tree be? (Deep enough that recursion is risky.)
Should the output match recursive preorder exactly? (Yes.)

Follow-ups to expect

"Why push right before left?"
"What's on the stack at any time?"
"How would you turn this into postorder?"
"Morris preorder?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview