LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List Solution in Python – A Step-by-Step Guide

What Is LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List?

In LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List, you’re given the root of a BST (e.g., a tree with values 4, 2, 5, 1, 3), and you need to convert it in-place into a sorted doubly linked list where:

• Each node’s left points to the previous node (or None for the head).
• Each node’s right points to the next node (or None for the tail).
• The list is sorted in ascending order (BST inorder property).

For example, a BST with root 4, left 2 (left 1, right 3), right 5 becomes a list: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5. You return the head (smallest value, 1). The conversion must be in-place, reusing the tree nodes without creating new ones.

Problem Statement

• Input: A Node object (root of a BST), where Node has val, left, right.
• Output: A Node object—the head of the sorted doubly linked list.
• Rules:
• Convert BST to sorted doubly linked list in-place.
• left points to previous, right to next.
• Return head (smallest value).

Constraints

• Number of nodes is in range [0, 2000].
• -1000 <= Node.val <= 1000.
• All values are unique.
• Input is a valid BST.

Examples

• Input: [4,2,5,1,3]
• Output: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 (head = 1).
• Input: [2,1,3]
• Output: 1 ↔ 2 ↔ 3 (head = 1).
• Input: []
• Output: None.

Understanding the Problem: Rewiring the Tree

To solve LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List in Python, we need to transform a BST into a sorted doubly linked list in-place, linking nodes in inorder sequence (smallest to largest). A naive idea might be to extract values, sort them, and build a new list—but that’s not in-place! Instead, we’ll use:

• Best Solution (Inorder Traversal with Pointer Manipulation): O(n) time, O(h) space—reshapes efficiently.
• Alternative Solution (Divide-and-Conquer with Merging): O(n) time, O(h) space—splits and joins.

Let’s dive into the inorder traversal solution with a clear, step-by-step explanation.

Best Solution: Inorder Traversal with Pointer Manipulation

Why This Is the Best Solution

The inorder traversal with pointer manipulation method is the top pick because it’s efficient—O(n) time, O(h) space (h = tree height)—and elegantly rewires the BST in-place using the natural sorted order of inorder traversal. It uses a recursive approach with global pointers to track the head and previous node, linking them as it goes, forming a circular list, then breaking it to a doubly linked list. It’s like threading a needle through the tree, stitching nodes into a sorted chain!

How It Works

Think of the BST as a tree you’re flattening:

• Step 1: Setup Pointers:
• self.head: Tracks smallest node (list start).
• self.prev: Tracks last visited node.
• Step 2: Inorder Traversal:
• Recurse left (smallest first).
• Process current node:
• If prev exists, link prev.right to current, current.left to prev.
• Update prev to current.
• If first node, set head.
• Recurse right.
• Step 3: Close and Open:
• After traversal, prev is tail, link to head (circular).
• Break circle: tail.right = None, head.left = None.
• Step 4: Why This Works:
• Inorder ensures sorted order (BST property).
• In-place linking reuses nodes, no extra space beyond recursion stack.
• It’s like weaving a sorted thread through the tree!

Step-by-Step Example

Example: [4,2,5,1,3]

• Tree:

4 / \ 2 5 / \ 1 3

• Traversal:
• Start: head = None, prev = None.
• 1: Leftmost, head = 1, prev = 1.
• 2: Left = 1, prev = 1, 1.right = 2, 2.left = 1, prev = 2.
• 3: Left done, prev = 2, 2.right = 3, 3.left = 2, prev = 3.
• 4: Left done, prev = 3, 3.right = 4, 4.left = 3, prev = 4.
• 5: Left done, prev = 4, 4.right = 5, 5.left = 4, prev = 5.
• Close: prev = 5, 5.right = head (1), 1.left = 5 (circular).
• Open: 5.right = None, 1.left = None.
• Result: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5, head = 1.

Example: [2,1,3]

• Traversal: 1 → 2 → 3, head = 1, prev = 3.
• Close: 3.right = 1, 1.left = 3.
• Open: 3.right = None, 1.left = None.
• Result: 1 ↔ 2 ↔ 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy code# Definition for a binary tree node.
class Node:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None

        # Step 1: Initialize pointers
        self.head = None  # First node (smallest)
        self.prev = None  # Last visited node

        # Step 2: Inorder traversal
        def inorder(node):
            if not node:
                return
            # Recurse left
            inorder(node.left)

            # Process current
            if self.prev:
                self.prev.right = node
                node.left = self.prev
            else:
                self.head = node  # First node
            self.prev = node

            # Recurse right
            inorder(node.right)

        # Run traversal
        inorder(root)

        # Step 3: Close and open circular list
        self.prev.right = self.head  # Tail to head
        self.head.left = self.prev   # Head to tail
        self.prev.right = None       # Break circle
        self.head.left = None        # Final doubly list

        return self.head

• Line 2-7: Node class (given):
• val, left, right for BST structure.
• Line 11-13: Handle empty tree, return None.
• Line 16-17: Initialize:
• self.head: Tracks list start (smallest).
• self.prev: Tracks previous node.
• Line 20-33: Inorder traversal:
• Line 23-24: Recurse left (smallest first).
• Line 26-30: Process current:
• If prev exists, link prev.right to node, node.left to prev.
• Else, set head (first node).
• Update prev to current.
• Line 32-33: Recurse right.
• Line 36-39: Close and open:
• prev.right = head, head.left = prev (circular).
• Break: prev.right = None, head.left = None.
• Line 41: Return head.
• Time Complexity: O(n)—inorder visits each node once.
• Space Complexity: O(h)—recursion stack, h = tree height.

This is like threading a sorted chain through the tree with a single pass!

Alternative Solution: Divide-and-Conquer with Merging

Why an Alternative Approach?

The divide-and-conquer with merging method splits the BST into left and right subtrees, converts them to doubly linked lists, and merges them with the root. It’s O(n) time and O(h) space—more structured but slightly more complex. It’s like breaking the tree into sorted lists and stitching them together!

How It Works

Picture it as splitting and joining:

• Step 1: Recursively convert left and right subtrees.
• Step 2: Merge left list, root, right list into one doubly linked list.
• Step 3: Return head of final list.

Step-by-Step Example

Example: [4,2,5,1,3]

• Split:
• Left (2,1,3): 1 ↔ 2 ↔ 3.
• Root: 4.
• Right: 5.
• Merge:
• Left (1 ↔ 2 ↔ 3) + 4: 1 ↔ 2 ↔ 3 ↔ 4.
• + Right (5): 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5.
• Result: Head = 1.

Code for Divide-and-Conquer Approach

Copy codeclass Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None

        # Convert tree to doubly linked list
        def convert(node):
            if not node:
                return None, None  # Head, tail

            # Convert left and right subtrees
            left_head, left_tail = convert(node.left)
            right_head, right_tail = convert(node.right)

            # Root as single node list
            node.left = node.right = None

            # Merge left, root, right
            head = tail = node
            if left_tail:
                left_tail.right = node
                node.left = left_tail
                head = left_head
            if right_head:
                node.right = right_head
                right_head.left = node
                tail = right_tail

            return head, tail

        head, _ = convert(root)
        return head

• Time Complexity: O(n)—each node processed once.
• Space Complexity: O(h)—recursion stack.

It’s a split-and-stitch transformer!

Comparing the Two Solutions

• Inorder Traversal (Best):
• Pros: O(n), O(h), simple and direct.
• Cons: Global state.
• Divide-and-Conquer (Alternative):
• Pros: O(n), O(h), structured.
• Cons: More merging steps.

Inorder wins for simplicity.

Additional Examples and Edge Cases

• []: None.
• [1]: 1 (self-linked).
• [2,1]: 1 ↔ 2.

Inorder handles all.

Complexity Breakdown

• Inorder: Time O(n), Space O(h).
• Divide-and-Conquer: Time O(n), Space O(h).

Inorder’s sleek.

Key Takeaways

• Inorder: Thread it through!
• Divide-and-Conquer: Split and join!
• BST: Inorder sorts.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Link That List

LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List in Python is a tree-flattening quest. Inorder traversal with pointers rewires it fast, while divide-and-conquer splits it smart. Want more tree fun? Try LeetCode 109: Convert Sorted List to Binary Search Tree or LeetCode 114: Flatten Binary Tree to Linked List. Ready to rewire? Head to Solve LeetCode 426 on LeetCode and link that list today!