Convert Binary Search Tree to Sorted Doubly Linked List

Problem Id: 426 Difficulty: Medium Tag: Linked List Tag: Divide an Conquer Tag: Tree


Intuition

We could first do an inorder traversal and mark its predecessor for each node. Then we could mark the nodes' successor in a loop.

Solution


"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if root is None:
            return None
        self.head = None
        self.prev = None
        # Mark all predecessor
        self._inorder_mark_right(root)
        self.head.left = self.prev
        # Mark all successor
        prev = self.head.left
        while prev != self.head:
            prev.left.right = prev
            prev = prev.left
        self.head.left.right = self.head
        return self.head

    def _inorder_mark_right(self, node):
        if node is None:
            return
        l, r = node.left, node.right
        self._inorder_mark_right(l)
        if self.head is None:
            self.head = node
        node.left = self.prev
        self.prev = node
        self._inorder_mark_right(r)