Difficulty: Medium
Category: Tree, Linked List, DFS
Companies: Amazon, Microsoft, Facebook

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

Think of the left and right pointers as synonymous to the previous and next 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: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Example 2:

Input: root = [2,1,3]
Output: [1,2,3]

Constraints

  • -1000 <= Node.val <= 1000
  • Node.left.val < Node.val < Node.right.val (BST property)
  • 1 <= Number of Nodes <= 1000

Solution Approaches

Key Insight: Use inorder traversal to visit nodes in sorted order, maintaining first and last nodes to build the doubly linked list.

Algorithm:

  1. Use inorder traversal to process nodes in sorted order
  2. Maintain global first and last pointers
  3. For each node, connect it to the previous node
  4. After traversal, connect first and last to make it circular

Time Complexity: O(n)
Space Complexity: O(h) where h is height of tree

class Solution:
    def __init__(self):
        self.first = None
        self.last = None

    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None

        self.inorder(root)

        # close circular list
        self.last.right = self.first
        self.first.left = self.last

        return self.first

    def inorder(self, node: 'Node') -> None:
        if not node:
            return

        self.inorder(node.left)

        if self.last:
            self.last.right = node
            node.left = self.last
        else:
            self.first = node

        self.last = node

        self.inorder(node.right)

Solution Explanation

Approach: Divide & conquer on tree (this problem)

Key idea: Difficulty:** Medium

How the code works: Difficulty: Medium Category: Tree, Linked List, DFS

  • Trees have no cycles — recursion is natural.
  • Combine results from left and right subtrees at each node.
  • Base case is usually null; height drives stack space.

Walkthrough — input root = [4,2,5,1,3], expected output [1,2,3,4,5]:

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

Implementation Details

Global Variables Approach

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None

        head = [None]
        tail = [None]

        self.inorder(root, head, tail)

        # close circular DLL
        head[0].left = tail[0]
        tail[0].right = head[0]

        return head[0]

    def inorder(self, node: 'Node', head: list, tail: list) -> None:
        if not node:
            return

        self.inorder(node.left, head, tail)

        if not head[0]:
            head[0] = node
        else:
            tail[0].right = node
            node.left = tail[0]

        tail[0] = node

        self.inorder(node.right, head, tail)

Circular Connection

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None

        stk = []
        first = None
        last = None
        curr = root

        while curr or stk:
            while curr:
                stk.append(curr)
                curr = curr.left

            curr = stk.pop()

            if not first:
                first = curr
            else:
                last.right = curr
                curr.left = last

            last = curr
            curr = curr.right

        # close circular list
        first.left = last
        last.right = first

        return first

Edge Cases

  1. Empty Tree: nullptr → return nullptr
  2. Single Node: [1] → circular list with one node
  3. Left Skewed: [1,null,2,null,3] → sorted order
  4. Right Skewed: [1,2,null,3] → sorted order

Follow-up Questions

  • What if the tree wasn’t a BST?
  • How would you handle duplicate values?
  • What if you needed a non-circular doubly linked list?
  • How would you optimize for very large trees?

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Optimization Techniques

  1. Inorder Traversal: Leverage BST property for sorted order
  2. Global Variables: Simplify state management
  3. In-place Transformation: No extra space for new nodes
  4. Circular Connection: Efficient circular list creation

Code Quality Notes

  1. Readability: Global variables approach is most intuitive
  2. Performance: All approaches have O(n) time complexity
  3. Space Efficiency: O(h) space for recursion stack
  4. Robustness: Handles all edge cases correctly

Key Takeaways

  • Pattern: Divide & conquer on tree (this problem)
  • Difficulty:** Medium
  • Category:** Tree, Linked List, DFS

References

Template Reference

Thinking Process

Difficulty: Medium

Category: Tree, Linked List, DFS

  • Trees have no cycles — recursion is natural.
  • Combine results from left and right subtrees at each node.
  • Base case is usually null; height drives stack space.
Linked list: pointer walk 1 2 3 slow → → fast (2x speed)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS O(n) O(h) Depth, path sum, subtree queries
BFS level-order O(n) O(w) Level traversal, zigzag
Inorder on BST O(n) O(h) Sorted order, successor
Divide & conquer on tree (this problem) O(n) O(h) Diameter, max path