Code Implementation

# 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: 'Node') -> 'Node':
        if not root:
            return None

        def dfs(node):
            nonlocal last, first
            if not node:
                return
            dfs(node.left)
            if last:
                last.right = node
                node.left = last
            else:
                first = node
            last = node
            dfs(node.right)

        first, last = None, None
        dfs(root)
        # Make it circular
        last.right = first
        first.left = last
        return first
      

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/

class Solution {
public:
    Node* first = nullptr;
    Node* last = nullptr;
    
    void dfs(Node* node) {
        if (!node) return;
        dfs(node->left);
        if (last) {
            last->right = node;
            node->left = last;
        } else {
            first = node;
        }
        last = node;
        dfs(node->right);
    }
    
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        dfs(root);
        last->right = first;
        first->left = last;
        return first;
    }
};
      

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/

class Solution {
    Node first = null;
    Node last = null;

    public void dfs(Node node) {
        if (node == null) return;
        dfs(node.left);
        if (last != null) {
            last.right = node;
            node.left = last;
        } else {
            first = node;
        }
        last = node;
        dfs(node.right);
    }

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        dfs(root);
        last.right = first;
        first.left = last;
        return first;
    }
}
      

/*
// Definition for a Node.
function Node(val, left, right) {
    this.val = val;
    this.left = left;
    this.right = right;
};
*/

var treeToDoublyList = function(root) {
    if (!root) return null;
    let first = null, last = null;

    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        if (last) {
            last.right = node;
            node.left = last;
        } else {
            first = node;
        }
        last = node;
        dfs(node.right);
    }

    dfs(root);
    last.right = first;
    first.left = last;
    return first;
};
      

Problem Description

You are given the root of a Binary Search Tree (BST). Your task is to convert this BST into a sorted circular doubly linked list in-place. Each node in the BST has a val (integer value), a left pointer (for the left child), and a right pointer (for the right child).

• After conversion, each node's left pointer should point to its predecessor, and its right pointer should point to its successor in the sorted order.
• The first node's left should point to the last node, and the last node's right should point to the first node, making the list circular.
• Do not create new nodes—reuse the existing tree nodes.
• There is exactly one valid solution for each BST.
• If the input is empty (root is null), return null.

Thought Process

The problem asks for an in-place transformation of a BST into a sorted doubly linked list, preserving the order and structure. The first instinct might be to perform an in-order traversal, collect all the nodes in a list, and then relink them as a doubly linked list. However, this would require extra space for the list, which is not optimal.

Since a BST's in-order traversal visits nodes in ascending order, we can leverage this property to connect nodes as we traverse, without needing extra space. The challenge is to properly connect the previous and current nodes during traversal, and finally, to link the head and tail to make the list circular.

By maintaining pointers to the previous (last visited) node and the first (smallest) node, we can adjust pointers as we traverse, ensuring that the doubly linked list is built correctly in one pass.

Solution Approach

We use an in-order traversal to process nodes in ascending order. The algorithm connects each node to its predecessor and successor as follows:

1. Initialize two pointers:
   • first: Points to the smallest (first) node in the list.
   • last: Points to the last processed node.
2. In-order DFS traversal:
   • For each node, recursively traverse the left subtree.
   • On visiting a node:
     • If last exists, connect last.right to current node, and current.left to last.
     • If last does not exist, set first to current node (this is the smallest node).
     • Update last to current node.
   • Recursively traverse the right subtree.
3. After traversal:
   • Connect first.left to last, and last.right to first to complete the circular doubly linked list.
4. Return first as the head of the list.

This approach is efficient and modifies the pointers in-place, with no extra data structures required.

Example Walkthrough

Consider the BST:

        4
       / \
      2   5
     / \
    1   3
  

Step-by-step traversal and linking:

1. Traverse left subtree of 4: go to 2
2. Traverse left subtree of 2: go to 1
3. 1 has no left child. Set first = 1, last = 1.
4. Back to 2: link 1.right = 2, 2.left = 1, update last = 2.
5. Traverse right subtree of 2: go to 3
6. 3 has no left child. Link 2.right = 3, 3.left = 2, update last = 3.
7. Back to 4: link 3.right = 4, 4.left = 3, update last = 4.
8. Traverse right subtree of 4: go to 5
9. 5 has no left child. Link 4.right = 5, 5.left = 4, update last = 5.
10. Traversal complete. Link first.left = last (1.left = 5) and last.right = first (5.right = 1) to make it circular.

The final doubly linked list is: 1 <-> 2 <-> 3 <-> 4 <-> 5 (circular).

Time and Space Complexity

• Brute-force approach:
  • Collect all nodes in a list (O(n)), then relink (O(n)).
  • Time: O(n)
  • Space: O(n) for the extra list
• Optimized in-place approach (current solution):
  • Each node is visited once in in-order traversal.
  • Time: O(n), where n is the number of nodes
  • Space: O(h) for recursion stack, where h is the tree height (O(log n) for balanced, O(n) for skewed)
  • No extra space for data structures; only pointer manipulation

Summary

This problem elegantly leverages the in-order traversal property of BSTs to transform the tree into a sorted, circular, doubly linked list in-place. By maintaining pointers to the first and last nodes, we can connect nodes as we traverse, ensuring both order and circularity. The solution is efficient, requires minimal extra space, and demonstrates a useful technique for in-place tree transformations.