6
\$\begingroup\$

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.

\$\endgroup\$
9
  • \$\begingroup\$ Do we write our own implementation of the binary tree object for our code? Are the characters of that counted? \$\endgroup\$
    – xnor
    Jun 27, 2014 at 20:19
  • \$\begingroup\$ @xnor Yes, you have to \$\endgroup\$
    – user26458
    Jun 27, 2014 at 20:39
  • \$\begingroup\$ Are the binary trees complete? \$\endgroup\$ Jun 27, 2014 at 21:36
  • \$\begingroup\$ @JoshuaTaylor not necessarily \$\endgroup\$
    – user26458
    Jun 27, 2014 at 22:20
  • 1
    \$\begingroup\$ You can't please everyone. The original challenge had a nice constraint on memory allocation that pleased me. Now I can copy all the three in new nodes and work on the copy. That said, Ray did post an answer (unlike me) so his opinion has more weight than mine. \$\endgroup\$
    – edc65
    Jun 30, 2014 at 21:51

5 Answers 5

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ You could shorten the result further by doing this: def T(p,q=None): if not p:return q; p.r=T(p.l,T(p.r,q)); r.l=p; return r \$\endgroup\$
    – Alexey
    Mar 16, 2015 at 11:24
1
\$\begingroup\$

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]);
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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 ;-)

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.