What is the time complexity of LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List?

The Python solution on this page uses O(n) auxiliary space.

Convert Binary Search Tree to Sorted Doubly Linked List — LeetCode 426 Python Solution

MediumLeetCode PremiumStackTreeDepth-First SearchBinary Search TreeLinked ListBinary TreeDoubly-Linked List

Problem: #426
Pattern: Linked List
Reading time: 6 min
Source: leetcode.com

The problem

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place. You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list.

Example

Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Python solution

Python

"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
        def dfs(root):
            if root is None:
                return
            nonlocal prev, head
            dfs(root.left)
            if prev:
                prev.right = root
                root.left = prev
            else:
                head = root
            prev = root
            dfs(root.right)

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

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List is filed here because LeetCode tags it Linked List and Doubly-Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List?: LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List is rated Medium on LeetCode.
What is the time complexity of LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List cover?: LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List is tagged Stack, Tree, Depth-First Search, Binary Search Tree, Linked List, Binary Tree and Doubly-Linked List on LeetCode.
Is LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List a premium problem?: Yes. LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.