426. Convert Binary Search Tree to Sorted Doubly Linked List - Detailed Explanation

The iterative solution in Java uses a stack (here a Deque for efficiency) to simulate the in-order traversal and links nodes similarly. We reused the traverseList helper (made static in MainRecursiveDemo) to print the outcome.

Both the recursive and iterative implementations in Python and Java produce the same correct result. You can test them with different BST inputs, including edge cases, to ensure they handle all scenarios.

Complexity Analysis

Regardless of the approach, the problem essentially performs an in-order traversal of the tree and adjusts pointers. Let N be the number of nodes in the BST.

• Time Complexity: O(N) for all approaches. We visit each node exactly once to adjust pointers (in-order traversal). Linking pointers is O(1) work per node. For instance, in the recursive and iterative solutions, each node is processed one time in the traversal. Even if using the intermediate list approach, collecting nodes is O(N) and linking them is another O(N), which is still O(N) overall.
• Space Complexity:
  • Recursive DFS: O(H) on the call stack, where H is the height of the tree. In the worst case (skewed tree), H = N (so O(N) stack space). If the tree is balanced, H ≈ log N. Aside from recursion stack, we use a constant number of pointers for linking.
  • Iterative with Stack: O(H) for the explicit stack in the best/average case. In worst case (skewed tree), the stack could hold O(N) nodes if all nodes are in one path. So worst-case space is O(N), but for balanced trees it's O(log N).
  • In-place modification: We are not creating new nodes, just repurposing pointers, so the space for nodes themselves is not extra (we modify in place). We only count auxiliary data structures. The final doubly linked list uses the same nodes as the tree.
  • Using an intermediate list: O(N) extra space for the list of nodes or values, plus O(N) for linking (if linking new Node objects, that’d be additional, but if reusing existing nodes then just the list cost). This is less space-efficient compared to the in-place methods above.
• Additional note: The output itself is using the same N nodes, arranged in a list. If we consider the circular list pointers as part of output, that’s still just the given nodes rearranged, so no extra memory beyond the original tree’s nodes.

In summary, the in-order traversal methods are linear in time and use O(N) space in the worst case (due to recursion or stack). This is optimal for this problem, since any solution must at least touch all N nodes to adjust pointers.

Step-by-Step Example Walkthrough

Let’s walk through Example 1 (BST with nodes 4,2,5,1,3) using the recursive in-order approach, to see how the pointers are updated at each step:

    4
   / \
  2   5
 / \
1   3

This is the initial BST structure. We will convert it into a sorted doubly linked list. The in-order traversal of this tree should visit nodes in the order: 1, 2, 3, 4, 5.

• Start at root (4): We begin an in-order traversal. The current node is 4. We first traverse its left subtree.
• Go left to node 2: Now current node is 2. Again, go left first (in-order).
• Go left to node 1: Current node is 1. Attempt to go left – but 1 has no left child, so we hit a leaf.
• Visit node 1: Since 1 has no left child, we process node 1. At this point, there is no previous node yet (this is the smallest node). So:
  • Set head = 1. (The head of our list will be the node with value 1.)
  • There is no prev to link to, because 1 is the first node. So we just set prev = 1.
• Traverse right of 1: Node 1 has no right child. So we return back up to its parent.
• Back at node 2: We've finished the left subtree of 2 (which was just node 1). Now we process node 2:
  • The prev is currently 1 (from the last step). So we link 1 and 2. Set 1.right = 2 and 2.left = 1. Now 1 ⇄ 2 are linked.
  • Update prev to 2 (the last node in our list is now 2).
  • Set head remains 1 (unchanged, as 1 is still the smallest).
• Go right to node 3: Now traverse the right subtree of 2. Node 3 becomes the current node.
• Node 3 has no left child: So we process 3 immediately:
  • prev is 2. Link 2 and 3: set 2.right = 3 and 3.left = 2. Now the list links 1 ⇄ 2 ⇄ 3.
  • Update prev to 3.
  • head is still 1.
• Node 3 has no right child: Return back up. We finished processing node 2 and its subtrees (so the entire left subtree of 4 is done, and we have 1 ⇄ 2 ⇄ 3 linked).
• Back at root 4: Now process node 4:
  • prev is 3. Link 3 and 4: set 3.right = 4 and 4.left = 3. The list is now 1 ⇄ 2 ⇄ 3 ⇄ 4.
  • Update prev to 4.
  • head stays 1.
• Go right to node 5: Traverse the right subtree of 4. Current node becomes 5.
• Node 5 has no left child: Process 5:
  • prev is 4. Link 4 and 5: set 4.right = 5 and 5.left = 4. Now we have 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5.
  • Update prev to 5.
  • head remains 1.
• Node 5 has no right child: The traversal is now complete. prev is pointing to 5 (the last node in sorted order). head is pointing to 1 (the first node).
• Make it circular: Finally, link the ends to make it a circular list:
  • Set 5.right = 1 (last node's next is head).
  • Set 1.left = 5 (head's previous is the last node).

Now the structure is a circular doubly linked list:

1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5
^               ^
|_______________|  (circular connection between 1 and 5)

• The head of the list is 1.
• 1.right → 2, 2.right → 3, 3.right → 4, 4.right → 5, and 5.right → 1 (circularly back to head).
• Similarly, 1.left → 5, 5.left → 4, 4.left → 3, 3.left → 2, 2.left → 1.

If we traverse starting at head (1) and follow right pointers, we get 1 → 2 → 3 → 4 → 5 and then back to 1, as expected. This matches the output [1,2,3,4,5].

The iterative approach would follow the same sequence of processing, though the mechanics (using a stack) differ internally. The end result and the order of linking would be the same.

Common Mistakes and How to Avoid Them

Beginners might run into a few pitfalls with this problem. Here are some common mistakes and tips to avoid them:

• Not handling the empty tree: Forgetting to check if root is null at the start. If you don’t handle this, your function might attempt to access properties of a null object. Always return null/None immediately for an empty input.

• Forgetting to set the head (smallest element): If your logic doesn’t correctly identify the first node in in-order traversal, you might never set the head of the list. This can lead to a null reference when you try to return or use the head. Ensure that when prev is null (meaning the node you’re visiting is the smallest so far), you record that node as head.

• Not updating the prev pointer: If you forget to update prev = current after linking, your next link will be wrong. The prev pointer should always point to the last node that was added to the list. Double-check that you update it in the loop or recursion after processing a node.

• Missing the final circular connection: A very common mistake is to build the doubly linked list in sorted order but forget to connect the tail and head at the end. The result in that case would be a straight doubly linked list (not circular). Always remember to do prev.right = head and head.left = prev after traversal is done. (Also ensure that prev and head are not null at that point — if the tree was empty, you should not perform this step.)

• Altering the tree structure incorrectly: Some might mistakenly attempt to detach nodes or create new nodes. Remember, we want an in-place conversion. You should only be reassigning the left and right pointers of existing nodes. Don’t create new Node objects or remove nodes from the tree; just relink them.

• Stack misuse in iterative approach: If using a stack, be careful with the loop conditions. A common bug is forgetting one of the conditions in the while loop (it should run while there are nodes to process or nodes in the stack). Also ensure you push all left descendants and correctly move to the right node after popping. Off-by-one errors in this process can lead to skipping nodes or infinite loops. Tracing the algorithm with a simple tree on paper can help verify your stack logic.

• Using global variables without resetting (in multiple test cases): If you implement this in a class with global prev and head (like the Java solution), and then call the function multiple times on different trees using the same instance, you might carry over state. To avoid this, reset or reinitialize your prev and head at the start of treeToDoublyList each time (or create a new Solution object per call). In our implementations, we handled this by setting them anew in each call.

• Not considering single-node behavior: Ensure that if the tree has one node, your logic sets that node’s left and right to itself. If you forget the circular step, a single node’s pointers might remain null which is incorrect (it should point to itself in a circular list). Our approach naturally handles this because for a single node, head and prev will be that node, and then we link it to itself at the end.

By keeping these points in mind and thoroughly testing with small cases (including edge cases like empty or single-node trees), you can avoid most of these common issues.

Edge Cases to Consider

Make sure your solution handles the following scenarios:

• Empty Tree: As discussed, if root is null, just return null (the resulting list is empty). No pointers to connect.

• Single Node Tree: The result should be a circular doubly linked list of length 1. The single node’s left and right pointers should both point to itself. (After our logic, head and prev will be this node, and we do node.right = node and node.left = node in the final step.)

• BST with Only Left Subtree (Skewed Left): e.g., a tree where each node only has a left child (like 5 <- 4 <- 3 <- 2 <- 1). This is essentially a descending linked list as a tree. The in-order traversal of this will visit nodes from the bottom (1) up to the top (5) in ascending order. The resulting doubly linked list should handle this gracefully (it will end up being the mirror of the tree: 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5). Ensure that your recursion/iteration can handle the depth and that you properly link each node. The head should be the bottom-left node.

• BST with Only Right Subtree (Skewed Right): Opposite of above, like 1 -> 2 -> 3 -> 4 -> 5 (each node only has a right child). In-order traversal will visit 1, then 2, etc., already in ascending order (since the tree itself is like an ascending list). The algorithm should link them in the same sequence. The head will be the root in this case (since root is the smallest in such a skewed tree). Check that your loop/recursion handles this (especially the iterative stack approach — if you only go right, you need to ensure the left pushing mechanism works when there are no left children).

• Two Nodes: This is a simple check – for example, a root with one child. If the child is left of root, then the list should be [child, root]. If the child is right of root, the list should be [root, child]. Make sure you handle setting head and linking for these small trees correctly.

• Duplicate Values: By constraint, this BST doesn’t have duplicates. But if it did (or in a binary tree that’s not a BST), in-order could still be used but defining sorted order with duplicates would need a convention (e.g., all duplicates appear consecutively). This is not applicable here due to unique values, so it simplifies things.

• Large Trees: With up to 2000 nodes, a recursive approach could potentially hit recursion depth issues if the tree is extremely skewed (depth 2000 might be okay, but near the limit for some languages). In Python, a skewed tree of 2000 might work but anything significantly larger could hit recursion depth limits. Our constraint is moderate, but it’s good to be aware. The iterative approach would handle skewed trees without recursion risk (but uses a large stack). Both should be fine for 2000 nodes, which is not huge. Just ensure efficiency (O(N)) which we have.

Testing various shapes of BST (balanced, skewed, etc.) will ensure your solution is robust across these edge cases.

Alternative Variations and Related Problems

This problem is a specific instance of tree-to-linked-list conversion. Here are some variations and related problems that you might find interesting for further practice:

• Flatten Binary Tree to Singly Linked List (LeetCode 114): This is a similar problem where you flatten a binary tree to a linked list in-place, but the catch is it’s a singly linked list using the right pointer (and you typically follow a pre-order traversal order). It’s a different traversal (pre-order vs in-order) and results in a singly linked list (not circular). The approach also uses recursion or iteration.

• Increasing Order Search Tree (LeetCode 897): This problem is almost like a simplified version of our BST-to-DLL, but it asks to rearrange the BST into a chain where each node has only a right child (like a singly linked list in ascending order). Essentially, it’s an in-order traversal that creates a right-skewed tree (or singly linked list) of all nodes in increasing order. You could solve it with the same in-order traversal idea, linking nodes via right pointers and ignoring left pointers.

• Convert Sorted Doubly Linked List to BST: While not a direct LeetCode problem, the inverse of what we did is a common interview question: Given a sorted doubly linked list, can you convert it back into a height-balanced BST? This would involve finding the middle element to be the root, etc. A related LeetCode problem is Convert Sorted List to BST (LC 109), where you’re given a sorted singly linked list and need to make a height-balanced BST. These problems explore the relationship in the opposite direction.

• Binary Tree to Doubly Linked List (Not necessarily BST): Some variations ask you to flatten a binary tree (not necessarily a BST) to a doubly linked list following the in-order sequence. The approach is basically the same (perform in-order traversal and link nodes). The difference is that the resulting list won’t be sorted unless the tree was a BST, but it will reflect the in-order ordering of the original tree. This is a common question on platforms like GeeksforGeeks for practicing pointer manipulation.

• Populating Next Right Pointers (LeetCode 116/117): While not an in-order problem, these tasks involve linking nodes at the same level in a binary tree (using a next pointer). It’s a different concept (level order and next pointers), but it’s another instance of pointer manipulation in trees to create linked structures. It can broaden your understanding of tree pointer problems.

• Threaded Binary Trees: The concept of a threaded tree is where null pointers of a binary tree are used to point to the in-order successor (or predecessor). This is related to the idea of converting to a linked list because essentially you’re linking nodes in order. Our problem fully converts the structure to a linked list, but learning about threaded trees (and Morris traversal) can be an interesting advanced topic that stems from similar ideas of linking inorder successors.