DSA interview question

Morris Preorder Traversal (O(1) Extra Space)

Hard · Data structures · Topics: tree, threaded binary tree

The problem

A memory-starved embedded device must traverse a large binary tree in preorder, but it can't afford a stack or recursion: only a couple of pointers. Morris traversal borrows the tree's unused right pointers. Before descending into a node's left subtree, it links that subtree's rightmost node (the node's inorder predecessor) back to the node, which leaves a "thread" to return along. When the traversal comes back through the thread, it removes it, so the tree ends up exactly as it started.

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

Function signature

vector<int> morrisPreorder(TreeNode* root);  // O(1) extra space; the tree is restored

Test cases

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

(Confirm: no stack and no recursion; the tree must be unchanged afterwards.)

How interviewers phrase it

"Traverse a binary tree in preorder using O(1) extra space: no recursion, no stack" (GeeksforGeeks "Morris Traversal for Preorder").

Clarifying questions to ask

May I modify the tree temporarily? (Yes, as long as it's restored.)
Is the tree shared with other threads during traversal? (Assume not, since temporary threads would confuse them.)
Must it be O(1) space? (Yes, which is the point of Morris.)

Follow-ups to expect

"What is the thread?"
"How does preorder differ from Morris inorder?"
"Why is it O(n) time even with the predecessor walks?"
"How is the tree restored?"
"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