Convert binary search tree into ordered linked list Write the shortest possible program that turns a binary search tree into an ordered doubly-linked list, by modifying the pointers to the left and the right children of each node.

Arguments: a pointer to the root of the binary tree.

Return value: a pointer to the head of the linked list.

The binary tree node has three fields:


the ordering key, an integer
a pointer to the left child
a pointer to the right child


The pointers should be modified so that "left child" points to the previous node of the list and "right child" points to the next node of the list.


Y̶o̶u̶'̶r̶e̶ ̶n̶o̶t̶ ̶a̶l̶l̶o̶w̶e̶d̶ ̶t̶o̶ ̶c̶r̶e̶a̶t̶e̶/̶a̶l̶l̶o̶c̶a̶t̶e̶ ̶m̶o̶r̶e̶ ̶n̶o̶d̶e̶s̶.
The tree and the list are both ordered increasingly.
You have to write the implementation of the node object.
The tree is not necessarily complete


Example:

input:
   5 &#60- root
  / \
 2   8
/ \ / \
1 4 6 9

output:
head -> 1-2-4-5-6-8-9

EDIT:
I removed the 1st rule, since people complained it was not possible to do using functional programming languages.
Python: 100

class N:l=r=v=None
def T(p,q=None):
 if not p:return q
 r=p.r=T(p.r,q)
 if r:r.l=p
 return T(p.l,p)


Ungolfed Version

class Node:
    left = right = value = None


def transform(node, next=None):
    """
    node: head node to convert
    next: next node for the tail node to connect
    return: The converted head
    """
    if not node:
        return next
    node.right = transform(node.right, next)
    if node.right:
        node.right.left = node
    return transform(node.left, node)


Instead of returning a (head, tail) pair, in my solution, a next node is passed as argument to the transform function so that it only need to return the head node. This make the code shorter and cleaner.