Convert Binary Search Tree to Sorted Doubly Linked List Problem

Problem

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

Examples

Example 1:

Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation:

We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

graph TD
	4 --- 2 & 5
	2 --- 1 & 3

The figure below shows the circular doubly linked list for the BST above. The “head” symbol means the node it points to is the smallest element of the linked list.

graph LR
	1 --> 2 --> 3 --> 4 -->5
	5 --> 4 --> 3 --> 2 --> 1

	HEAD --> 1
	1 --> 5
	5 --> 1

Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first element of the linked list.

The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Solution

Method 1 - Using Recursion

To transform a Binary Search Tree (BST) to a sorted circular doubly linked list (DLL) in place, we need to perform an in-order traversal of the tree. During traversal, we rearrange the pointers of the nodes such that:

The left pointer of each node points to its predecessor.
The right pointer of each node points to its successor.

We need to keep track of nodes visited during traversal to set the pointers correctly and eventually make the list circular by connecting the first and last nodes.

Approach

Define a helper function to perform in-order traversal.
Maintain a reference to the previous node visited (pre) and the head of the list (head).
During traversal:
- If pre is not None, link the pre.right to the current node and the current node’s left to pre.
- Update pre to the current node.
- Update head if this is the first node being visited.
After the traversal, link the head and the last nodes to form a circular doubly linked list.
Return head as the smallest node.

Code

Java

class Solution {
    class Node {
        int val;
        Node left;
        Node right;
        Node(int x) { val = x; left = null; right = null; }
    }
    
    private Node pre = null;
    private Node head = null;
    
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        inOrder(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    
    private void inOrder(Node curr) {
        if (curr == null) return;
        inOrder(curr.left);
        if (pre != null) {
            pre.right = curr;
            curr.left = pre;
        } else {
            head = curr;
        }
        pre = curr;
        inOrder(curr.right);
    }
}

Python

class Solution:
    class Node:
        def __init__(self, val: int):
            self.val = val
            self.left: Optional['Node'] = None
            self.right: Optional['Node'] = None

    def __init__(self):
        self.pre: Optional['Solution.Node'] = None
        self.head: Optional['Solution.Node'] = None

    def treeToDoublyList(self, root: Optional['Solution.Node']) -> Optional['Solution.Node']:
        if not root:
            return None
        self.inOrder(root)
        self.head.left = self.pre
        self.pre.right = self.head
        return self.head

    def inOrder(self, curr: Optional['Solution.Node']):
        if not curr:
            return
        self.inOrder(curr.left)
        if self.pre:
            self.pre.right = curr
            curr.left = self.pre
        else:
            self.head = curr
        self.pre = curr
        self.inOrder(curr.right)

Complexity

⏰ Time complexity: O(n) where n is the number of nodes in the tree.
🧺 Space complexity: O(1) for additional space if we disregard the recursive stack space used in traversal.

Problem#

Examples#

Solution#

Method 1 - Using Recursion#

Approach#

Code#

Java#

Python#

Complexity#