convert binary search tree to deque inplace

   4
 2   6
1 3 5 7

to

1 2 3 4 5 6 7

Node's left and right act as previous and next. Convert while dfs backtracking.

bst-to-deque-main(root):
    if root == null:
        throw
    return bst-to-deque(root)
    
{head, tail} bst-to-deque(n):
    if n == null:
        return null
    head = tail = n
    leftdq = bst-to-deque(n.left)
    if leftdq != null:
        head = leftdq.head
        leftdq.tail.right = n
        n.left = leftdq.tail
    rightdq = bst-to-deque(n.right)
    if rightdq != null:
        tail = rightdq.tail
        n.right = rightdq.head
        rightdq.head.left = n
    return {head, tail}

[Hat tip to ctci]