DSA interview question

Preorder, Inorder and Postorder in a Single DFS

Easy · Data structures · Topics: tree, stack

The problem

A tree-visualisation tool shows all three depth-first orders side by side, and walking the tree three times is wasteful for large trees. A single recursive DFS visits every node at three moments: on the way down, which is its preorder position; between its two subtrees, its inorder position; and on the way back up, its postorder position. Recording the node into three lists at those three moments produces all three traversals in one pass.

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 allTraversals(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, null, 2, 3]`	`pre [1,2,3] in [1,3,2] post [3,2,1]`
`[1, 2]`	`pre [1,2] in [2,1] post [2,1]`
`[1]`	`pre [1] in [1] post [1]`
`[]`	`pre [] in [] post []`

(Confirm: one traversal of the tree fills all three lists; the order within each list is the standard definition.)

How interviewers phrase it

"Print the preorder, inorder and postorder traversals of a binary tree using a single traversal."

Clarifying questions to ask

Is recursion allowed? (Yes here; the iterative version uses a stack of (node, state) pairs.)
Should the three lists be returned separately? (Yes.)
How deep can the tree be?

Follow-ups to expect

"What are the three moments?"
"Why is one pass enough?"
"Iterative version?"
"Where is this useful?"
"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