Convert BST to sorted doubly list
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Convert a binary search tree into a sorted doubly linked list in-place. Reuse the existing tree nodes: the left pointer becomes prev and the right pointer becomes next. Do not allocate new nodes. Return the head of the doubly linked list. Ensure the list is sorted in nondecreasing order according to an in-order traversal, and specify how you handle duplicate keys. Provide both a recursive and an iterative solution, and analyze time and space complexity. Follow-ups:
(
1) Modify your solution to produce a circular doubly linked list.
(
2) If recursion is forbidden, how do you guarantee O(
1) auxiliary space aside from the output pointers (e.g., Morris traversal)?
Quick Answer: This question evaluates understanding of binary search tree properties, in-order traversal, in-place pointer manipulation, and algorithmic complexity when converting tree nodes into a sorted doubly linked list.
Given BST level-order values, return the sorted values that the in-place doubly linked list would contain.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([4,2,5,1,3],)
Expected Output: [1, 2, 3, 4, 5]
Explanation: In-order list.
Input: ([],)
Expected Output: []
Explanation: Empty tree.
Input: ([1],)
Expected Output: [1]
Explanation: Single node.
Hints
- Model object-style prompts as arrays or operation streams when needed.
- Handle empty and boundary cases before the main logic.