DSA interview question

Iterative Inorder Traversal

Easy · Data structures · Topics: tree, stack

The problem

A database engine iterates over the keys of a binary search tree in sorted order, but its trees can be very deep, and recursion risks a stack overflow. The iterative inorder traversal mimics the recursion with an explicit stack. Walk as far left as possible, pushing every node on the way. Then pop one, record it, and continue from its right child. The stack always holds the ancestors whose left subtrees are still being processed.

Example: [5, 3, 7, 2, 4, 6, 8] (a BST) → [2, 3, 4, 5, 6, 7, 8].

Function signature

vector<int> inorderIterative(TreeNode* root);

Test cases

Input (level order)	Output	Explanation
`[1, null, 2, 3]`	`[1, 3, 2]`
`[1, 2, 3, 4, 5, 6, 7]`	`[4, 2, 5, 1, 6, 3, 7]`
`[5, 3, 7, 2, 4, 6, 8]`	`[2, 3, 4, 5, 6, 7, 8]`	A BST comes out sorted
`[1, 2, null, 3]`	`[3, 2, 1]`	A left chain
`[]`	`[]`

(Confirm: no recursion; the output must equal recursive inorder.)

How interviewers phrase it

"Return the inorder traversal of a binary tree without recursion" (LeetCode 94's follow-up).

Clarifying questions to ask

May I use a stack? (Yes; Morris traversal is the O(1)-space variant.)
How deep can the tree be?
Is it a BST? (Doesn't matter, but it's a common use.)

Follow-ups to expect

"What does the stack contain?"
"Why move to the right child after recording?"
"How is this used as a BST iterator?"
"Morris inorder?"
"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