LC: 426. Convert Binary Search Tree to Sorted Doubly Linked List - spiralgo/algorithms GitHub Wiki

426. Convert Binary Search Tree to Sorted Doubly Linked List

The Essence:

• The left-right pointers of the BST nodes can be used as prev-next pointers of the linked lists.
• The first value is the left-most node of the tree. Since this originally no node to connect a sentinel node needs to be created to temporarily connect it.
• A root should be connected to the largest value in its left sub-tree as the previous node. Since the largest value can be some right child of its left child, another pointer needs to be used to keep track of the last largest node.
• In order to create the small-middle-large sequence of the sorted list, first left nodes, then the current root, then the right nodes should be processed.

Details:

The sentinel node is initially the last node. The last node as updated for each node processed in the order described above (In-order traversal). At the end, the right of the sentinel node (first node) should be connected with the last node, which is at the end the actual last node.