DSA interview question

Postorder Traversal Using One Stack

Easy · Data structures · Topics: tree, stack

The problem

The same build system from before now runs on a device with little memory, so the second stack (which holds every node) is too expensive. With one stack, the challenge is knowing, when you look at a node on top of the stack, whether its right subtree has already been processed. Track the last node recorded. A node on top may be recorded if it has no right child or if its right child was the last node recorded. Otherwise, go and process its right subtree first.

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

Function signature

vector<int> postorderOneStack(TreeNode* root);

Test cases

Input (level order)	Output	Explanation
`[1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]`	`[4, 6, 7, 5, 2, 9, 8, 3, 1]`
`[2, 1, 3]`	`[1, 3, 2]`
`[1, null, 2, null, 3]`	`[3, 2, 1]`	A right chain: the tricky case
`[1]`	`[1]`
`[]`	`[]`

(Confirm: one explicit stack plus O(1) extra pointers; the output equals recursive postorder.)

How interviewers phrase it

"Implement postorder traversal using only one stack" (GeeksforGeeks).

Clarifying questions to ask

May I keep a few extra pointers? (Yes: cur and last.)
Is recursion forbidden? (Yes.)
Can the tree be deep and skewed? (Yes: the stack then holds O(h) nodes.)

Follow-ups to expect

"Why is postorder harder than preorder or inorder iteratively?"
"What does last tell you?"
"Why not pop the node before checking?"
"How does this compare to the two-stack method?"
"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