Flatten Binary Search Tree to Circular Doubly Linked List

Problem

Given a Binary Search Tree (BST), flatten it into a Circular Doubly Linked List (CDLL) in place. The nodes of the CDLL should be arranged in sorted order as per the BST's in-order traversal.

Examples

     BST:
           4
          / \
         2   5
        / \
       1   3

Input: root = [4,2,5,1,3]
Output:  1 <-> 2 <-> 3 <-> 4 <-> 5

->1 <-> 2 <-> 3 <-> 4 <-> 5 <- \
\___________________________ ___\

Explanation:
The in-order traversal of BST yields [1, 2, 3, 4, 5], and these are connected in sorted order with circular links.

Constraints

1. The BST will not have duplicate values.
2. The CDLL's right pointers will act as the "next pointers," and left pointers will act as the "previous pointers."
3. The head and tail of the CDLL must be connected to form a circular structure.

Solution

Method 1 - Inorder traversal

To flatten the BST into a CDLL:

• In-order Traversal naturally provides sorted order of nodes.
• A single node can be transformed into a self-loop CDLL by pointing its left and right pointers back to itself.
• Efficient Concatenation of sublists is performed by treating them as circular doubly linked lists. After converting left and right subtrees recursively, append them and the root node together in sorted circular order.

How to make the DLL circular?

Instead of scanning the list to find the tail (which would take O(n)), we can perform circular connections during traversal:

1. A standalone node is circular when its left and right pointers point to itself.
2. To concatenate two circular lists:
   • Connect the tail of the first list to the head of the second list.
   • Connect the tail of the second list back to the head of the first list.

Approach

1. Recursively divide the BST into left and right subtrees until reaching leaf nodes.
2. Convert each leaf node into a circular DLL using pointer manipulation.
3. Concatenate the left subtree, root, and right subtree circular lists in sorted order:
   • Make root a standalone circular DLL.
   • Use efficient concatenation for combining three lists.
4. Return the final circular DLL.

Code

Java

public class Solution {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
            left = right = null;
        }
    }

    public TreeNode flattenBST(TreeNode root) {
        if (root == null) {
            return null;
        }

        // Convert left and right subtrees to circular DLLs recursively
        TreeNode left = flattenBST(root.left);
        TreeNode right = flattenBST(root.right);

        // Convert root into a standalone circular DLL
        root.left = root;
        root.right = root;

        // Concatenate left, root, and right sublists
        left = concatCircularDLL(left, root);
        left = concatCircularDLL(left, right);

        return left; // Return the head of the circular doubly linked list
    }

    private TreeNode concatCircularDLL(TreeNode head1, TreeNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        // Find the tails of both circular lists
        TreeNode tail1 = head1.left; // Last node of list 1
        TreeNode tail2 = head2.left; // Last node of list 2

        // Connect list1's tail to head2
        tail1.right = head2;
        head2.left = tail1;

        // Connect list2's tail to head1
        tail2.right = head1;
        head1.left = tail2;

        return head1; // Return the merged circular list
    }
}

Python

class Solution:
    def flattenBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        # Convert left and right subtrees to circular DLLs recursively
        left = self.flattenBST(root.left)
        right = self.flattenBST(root.right)

        # Convert root into a standalone circular DLL
        root.left = root
        root.right = root

        # Concatenate left, root, and right sublists
        left = self.concatCircularDLL(left, root)
        left = self.concatCircularDLL(left, right)

        return left  # Return the head of the circular doubly linked list

    def concatCircularDLL(
        self, head1: Optional[TreeNode], head2: Optional[TreeNode]
    ) -> Optional[TreeNode]:
        if not head1:
            return head2
        if not head2:
            return head1

        # Find the tails of both circular lists
        tail1 = head1.left  # Last node of list 1
        tail2 = head2.left  # Last node of list 2

        # Connect list1's tail to head2
        tail1.right = head2
        head2.left = tail1

        # Connect list2's tail to head1
        tail2.right = head1
        head1.left = tail2

        return head1  # Return the merged circular list

Complexity

• ⏰ Time complexity: O(n). Each node is visited exactly once during recursion, and pointer manipulations are constant-time.
• 🧺 Space complexity: O(h). The recursive stack depth corresponds to the height (h) of the tree. In a balanced BST, h = O(log n). In the worst case (skewed tree), h = O(n).