DSA interview question

Morris Inorder Traversal (O(1) Extra Space)

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

The problem

A database iterates the keys of a huge binary search tree in sorted (inorder) order on a server where every byte of stack counts. Morris inorder traversal uses no stack and no recursion. It temporarily threads each node's inorder predecessor back to the node and walks back along the thread after finishing the left subtree. The node is recorded when the thread is removed, because that's the moment its left subtree is complete.

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

Function signature

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

Test cases

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

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

How interviewers phrase it

"Do an inorder traversal of a binary tree using O(1) extra space" (the Morris traversal; LeetCode 94 follow-up).

Clarifying questions to ask

May the tree be modified temporarily? (Yes, if restored.)
Is concurrent access possible? (Assume not.)
Is O(h) space acceptable instead? (No: the target is O(1).)

Follow-ups to expect

"When exactly is a node recorded?"
"Why is the predecessor the right node to thread?"
"Total time?"
"Uses?"
"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