LeetCode 426 - Convert Binary Search Tree to Sorted Doubly Linked List

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

/**
 * Solution for LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List
 * 
 * Problem: Convert a Binary Search Tree (BST) to a sorted Circular Doubly Linked List.
 * The conversion should be done in-place, meaning we should reuse the tree nodes.
 * 
 * Time Complexity: O(N) where N is the number of nodes in the tree
 * - We need to visit each node exactly once during the inorder traversal
 * 
 * Space Complexity: O(H) where H is the height of the tree
 * - In worst case (skewed tree), H = N
 * - In balanced tree, H = log N
 * - Space is used by the recursive call stack
 */
public class BSTToDoublyLinkedList {
    // Node class definition for the tree
    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    // Keep track of the last node we processed
    private Node lastNode = null;
    // Keep track of the first node for connecting the circular list
    private Node firstNode = null;

    /**
     * Main method to convert BST to Doubly Linked List
     * @param root Root of the binary search tree
     * @return Head of the resulting circular doubly linked list
     */
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }

        // Perform inorder traversal to process nodes in sorted order
        inorderTraversal(root);

        // Connect the first and last nodes to make it circular
        firstNode.left = lastNode;
        lastNode.right = firstNode;

        return firstNode;
    }

    /**
     * Helper method to perform inorder traversal and link nodes
     * @param currentNode Current node being processed
     */
    private void inorderTraversal(Node currentNode) {
        if (currentNode == null) {
            return;
        }

        // Process left subtree
        inorderTraversal(currentNode.left);

        // Process current node
        if (lastNode != null) {
            // Link the previous node (lastNode) with current node
            lastNode.right = currentNode;
            currentNode.left = lastNode;
        } else {
            // If this is the first node we're processing
            firstNode = currentNode;
        }
        lastNode = currentNode;

        // Process right subtree
        inorderTraversal(currentNode.right);
    }

    /**
     * Helper method to create a sample BST for testing
     */
    public static Node createSampleBST() {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        return root;
    }

    /**
     * Helper method to print the doubly linked list
     */
    public static void printDoublyLinkedList(Node head) {
        if (head == null) return;

        Node current = head;
        System.out.print("Forward traversal: ");
        do {
            System.out.print(current.val + " ");
            current = current.right;
        } while (current != head);
        System.out.println();
    }

    /**
     * Main method for testing
     */
    public static void main(String[] args) {
        BSTToDoublyLinkedList solution = new BSTToDoublyLinkedList();

        // Create a sample BST
        Node root = createSampleBST();

        // Convert BST to doubly linked list
        Node head = solution.treeToDoublyList(root);

        // Print the result
        printDoublyLinkedList(head);
    }
}