PPractick

The problem

A UI framework stores a menu as a binary tree but needs to render it as a flat list in preorder, reusing the same nodes: each node's right pointer becomes "next" and every left pointer becomes null. It must be done in place. The O(1)-space approach is Morris-like. For each node with a left subtree, attach the node's current right subtree to the rightmost node of the left subtree (the last node the left part visits in preorder), move the left subtree to the right, and continue down the right pointers.

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

Function signature

void flatten(TreeNode* root);  // in place: right = next in preorder, left = nullptr

Test cases

Input (level order)	Output (level order after flattening)	Explanation
[1, 2, 5, 3, 4, null, 6]	[1, null, 2, null, 3, null, 4, null, 5, null, 6]
[1, 2]	[1, null, 2]
[1, null, 2, 3]	[1, null, 2, null, 3]
[0]	[0]
[]	[]

(Confirm: the resulting list follows preorder; all left pointers must be null; no new nodes.)

How interviewers phrase it

• "Given the root of a binary tree, flatten it into a linked list in place, using the right pointers in preorder order" (LeetCode 114).

Clarifying questions to ask

1. Preorder order? (Yes.)
2. Must it be in place? (Yes, and O(1) extra space is the follow-up.)
3. Should left pointers be set to null? (Yes.)

Follow-ups to expect

1. "Why the rightmost node of the left subtree?"
2. "Recursive alternative?"
3. "Stack alternative?"
4. "Why is the rewiring approach O(n)?"
5. "Complexity?"

Related questions

• Maximum Depth in BT Medium
• Check for balanced binary tree Medium
• Maximum path sum Medium
• Check if two trees are identical or not Medium
• Boundary Traversal Medium
• Vertical Order Traversal Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in