Rule
In-order traversal of a BST visits nodes in ascending order. Link each visited node to the previous one, then connect head and tail.
BST · In-order DFS · LeetCode 426
Convert BST to Sorted Circular Doubly Linked List
Convert a BST in-place by reusing left as prev and right as next. In-order traversal gives sorted order for free; one final stitch closes the circle.
In-order DFSPointer RewiringCircular DLL
Key concepts at a glance — for those who already know the basics.
How to Think
1Run DFS in-order: left, node, right.
2Use head for the first visited node and prev for the last linked node.
3At each node: set prev.right = node and node.left = prev.
4After traversal: head.left = tail, tail.right = head.
Diagram
1⇄2⇄3⇄4⇄5(circular: tail ↔ head)
Complexity
Time
O(n)
Each node is visited exactly once.
Space
O(h)
Recursion stack only. Balanced: O(log n), skewed: O(n).
Common Mistakes
- Missing circular close: head.left = tail and tail.right = head.
- Using pre-order/post-order and expecting sorted order.
- Forgetting that this is in-place pointer rewiring (no new nodes).