Convert binary search tree into ordered linked list

Question

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 <- 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.

Answer 1

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.

Answer 2

Javascript 238 (163 not including the input tree declaration/initialization)

Tested in google chrome. To see the result, open the javascript console and traverse any node of the list.

jsfiddle: http://jsfiddle.net/49grd/1/

b={val:5,n1:{val:2,n1:{val:1},n2:{val:4}},n2:{val:8,n1:{val:6},n2:{val:9}}}
o=[]
function r(t){if(t.n1)r(t.n1);o.push(t);if(t.n2)r(t.n2);}
r(b);
for(var i=0;i<o.length;i++){if(o[i-1])o[i].n1=o[i-1];if(o[i+1])o[i].n2=o[i+1];}
console.dir(o[0]);

Ungolfed:

jsfiddle avbailable here: http://jsfiddle.net/s8PsU/

var binaryTree = 
{   
    val: 5,
    n1: {
        val: 2,
        n1: { val: 1},
        n2: { val: 4}
    },
    n2: {
        val: 8,
        n1: {val: 6},
        n2: {val: 9}
    }        
}

var orderedNodes = []

function traverse(t)
{
if(t.n1)
    traverse(t.n1);
orderedNodes.push(t);    
if(t.n2)
    traverse(t.n2);
}
traverse(binaryTree);

for(var i = 0; i < orderedNodes.length; i++)
{
if(orderedNodes[i-1])
    orderedNodes[i].n1 = orderedNodes[i-1];
if(orderedNodes[i+1])
    orderedNodes[i].n2 = orderedNodes[i+1];
}

console.dir(orderedNodes[0]);

Answer 3

Scala - (207/188) Characters

class n(a:n,b:Int,c:n){var l:n=a;var n:Int=b;var r:n=c}def t(r:n):(n,n)=(if(r.l==null)r
else{val y=t(r.l);r.l=y._2;y._2.r=r;y._1},if(r.r==null)r
else{val y=t(r.r);r.r=y._1;y._1.l=r;y._2})
def a(r:n)=t(r)._1

Without the function a wich just gets the head of the list, this are 188 characters.

Idea is: return a tuple wich consist of the most left element of you and your children and the most right element. Also link your left element to the most element of your left children and your right element to the most left element of your right children.

Code for printing the list:

def printN(r:n)=if(r==null)"null" else (r.n + "->" +printN(r.r))

Ungolfed:

class Node(a:n,b:Int,c:n){//our Node Class
   var l:Node=a //left child
   var n:Int=b //data of the node
   var r:Node=c //right cild
}
def traverse(r:Node):(Node,Node)=(//return a pair
        //get smallest known element
        if(r.l==null) r //smallest is identity if left child is null
        else { //sethighest of traverse of left child as left child
           val y=traverse(r.l)
           r.l=y._2 //left child is highest of traverse left child
           y._2.r=r //and right of this is me
           y._1 //return the currently smallest known element (maybe allways the smallest?
        },
        //get highest known element
        if(r.r==null) r //if right is null, current node is the highest known
        else { 
           val y=ttraverse(r.r) //traverse right child
           r.r=y._1 //set pointers for list
           y._1.l=r
           y._2 //return most right child of right child
        }
)//end of return pair
def traverseWrapper(r: Node)=t(r)._1 //just return the smallest element

Note that the list is now double linked, it is possible to ignore the back links and save characters (but this is too ugly).

Bring my first and second semester labs back to mind ;-)

Answer 4

C: 79 114

I'm not sure exactly how this is supposed to be scored, so if someone thinks that other parts of my code should be counted as well, please say so.

Here's the function that does the conversion:

t*f(t*n,t*h){static t*p=0;n?f(n->l,h),(p?(n->l=p),p->r=n:(h=n)),p=n,f(n->r,h):0;t*r=h;for(;r->l;r=r->l);return r;}

This is the struct that I use to represent a tree:

typedef struct n {
        int o;
        struct n* l;
        struct n* r;
} t;

You can see the rest of the code that I used to test it here (re-compile it, it uses STDIN). Here's a sample run:

$ ./tree2list < in
Insert nodes to tree:
Tree traversal:
-527
-7
0
2
3
6
8
23
63
conversion done
List traversal:
-527
-7
0
2
3
6
8
23
63

The contents of the file in:

6
8
2
3
0
-7
23
63
-527

I used code from here to help me fix my conversion algorithm.

Edit: I didn't notice that we're supposed to return a pointer to the list, so I still need to fix that. Fixed.

Answer 5

Haskell: 96

In this solution, new nodes are created, which violate the first rule. However, creating new nodes seems unavoidable in pure functional style code.

data N=N Int N N|L
f L=[]
f(N v l r)=f l++v:f r
g _[]=L
g p(x:y)=n where n=N x p$g n y
t=g L .f

Ungolfed Version

data Node = Node Int Node Node | Leaf

flatten :: Node -> [Int]
flatten Leaf = []
flatten (Node value left right) = flatten left ++ [value] ++ flatten right

link :: Node -> [Int] -> Node
link _ [] = Leaf
link prev (x:xs) = node where
    node = Node x prev $ link node xs

transform = link Leaf . flatten

Some code for testing:

toList Leaf = []
toList (Node v l r) = v:toList r

toReverseList' Leaf = []
toReverseList' (Node v l r) = v:toReverseList' l

toReverseList node@(Node v l Leaf) = toReverseList' node
toReverseList (Node v l r) = toReverseList r
toReverseList Leaf = []

t = Node 4 (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf)) (Node 5 Leaf Leaf)

main = do
    print $ toList $ transform t
    print $ toReverseList $ transform t