DSA interview question

Postorder Traversal Using Two Stacks

Easy · Data structures · Topics: tree, stack

The problem

A build system must compile modules so that every dependency is built before the module that needs it: children before the parent, which is postorder. The team wants it without recursion. The two-stack trick uses one observation: postorder is the reverse of "root, right, left". Produce root-right-left with an ordinary stack (like iterative preorder, but pushing left before right), push each popped node onto a second stack, and read that stack from top to bottom.

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

Function signature

vector<int> postorderTwoStacks(TreeNode* root);

Test cases

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

(Confirm: no recursion; the output equals recursive postorder.)

How interviewers phrase it

"Implement postorder traversal of a binary tree using two stacks" (GeeksforGeeks).

Clarifying questions to ask

Is O(n) extra space acceptable? (Yes: the second stack holds every node.)
Is recursion forbidden? (Yes, for this version.)
Should the output match the recursive order exactly? (Yes.)

Follow-ups to expect

"Why does reversing root-right-left give postorder?"
"Why push left before right on the first stack?"
"Can you avoid the second stack?"
"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