Leetcode 0426 Convert Binary Search Tree to Sorted Doubly Linked List

Problem statement

https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

Solution

Construct doubly linked list L1 = lft_head...lft_tail for left subtree, L2 = rgh_head...rgh_head for right subtree and then combine them in one big doubly linked list L1 + root + L2 in O(1). When we have leafs, create one-elements double linked lists. Do not forget the cases, when we have only left or only right children.

Complexity

Time complexity is O(n), space complexity is O(h) due to recursion stack.

Code

class Solution:
    def treeToDoublyList(self, root):
        def dfs(node):
            if node is None:
                return None, None
                
            lft_head, lft_tail = dfs(node.left)
            rgh_head, rgh_tali = dfs(node.right)
            
            if lft_head:
                lft_tail.right = node
                node.left = lft_tail
            if rgh_head:
                node.right = rgh_head
                rgh_head.left = node
            
            head = lft_head or node or rgh_head
            tail = rgh_tali or node or lft_tail
            
            return head, tail

        if root is None: return None
        
        head, tail = dfs(root)
        tail.right = head
        head.left = tail

        return head

Remark

There is also solution with O(1) complexity using inorder traversal. See problems 0108, 0109, which are opposite: we need to convert List (Single-Linked) to Balanced BST.