DSA interview question

Preorder, Inorder and Postorder in One Iterative Traversal

Easy · Data structures · Topics: tree, stack

The problem

A tree-inspection tool runs on threads with tiny call stacks, so recursion is out, yet it still wants all three depth-first orders from a single pass. Put (node, state) pairs on one explicit stack. State 1 means the node was just reached: record its preorder position and go left. State 2 means the left subtree is done: record its inorder position and go right. State 3 means both subtrees are done: record its postorder position and pop it. Each node passes through the three states exactly once.

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

Function signature

void allTraversalsIterative(TreeNode* root, vector<int>& pre, vector<int>& in, vector<int>& post);

Test cases

Input (level order)	Output	Explanation
`[1, 2, 3, 4, 5, 6, 7]`	`pre [1,2,4,5,3,6,7] in [4,2,5,1,6,3,7] post [4,5,2,6,7,3,1]`
`[1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]`	`pre [1,2,4,5,6,7,3,8,9] in [4,2,6,5,7,1,3,9,8] post [4,6,7,5,2,9,8,3,1]`
`[1, null, 2, 3]`	`pre [1,2,3] in [1,3,2] post [3,2,1]`
`[1]`	`pre [1] in [1] post [1]`
`[]`	`pre [] in [] post []`

(Confirm: a single explicit stack and no recursion; all three lists are filled in one pass.)

How interviewers phrase it

"Find the preorder, inorder and postorder traversals of a binary tree in one traversal" (GeeksforGeeks), with an iterative solution expected.

Clarifying questions to ask

Iterative? (Yes, a single stack.)
Should the three results be separate lists? (Yes.)
Can the tree be empty? (Yes.)

Follow-ups to expect

"What do the states mean?"
"Why keep the node on the stack between states?"
"How does this relate to the recursive version?"
"Memory?"
"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