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.