Examples: BST To sorted List - rFronteddu/general_wiki GitHub Wiki

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

// Definition for a doubly linked list node.
class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;
    DoublyListNode(int x) { val = x; }
}

public class BSTToDoublyLinkedList {
    private DoublyListNode head;
    private DoublyListNode prev;

    public DoublyListNode bstToDoublyLinkedList(TreeNode root) {
        if (root == null) return null;
        
        head = null;
        prev = null;
        
        inorderTraversal(root);
        
        return head;
    }
    
    private void inorderTraversal(TreeNode node) {
        if (node == null) return;
        
        // Traverse left subtree
        inorderTraversal(node.left);
        
        // Process current node
        DoublyListNode current = new DoublyListNode(node.val);
        if (head == null) {
            head = current; // Update head if it's null
        } else {
            prev.next = current; // Connect previous node's next pointer to current node
            current.prev = prev; // Connect current node's prev pointer to previous node
        }
        prev = current; // Update prev to current node
        
        // Traverse right subtree
        inorderTraversal(node.right);
    }
}