## Convert binary search tree into ordered linked list

6

2

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.

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.

Kind of a recursive DFS? – Magic Octopus Urn – 2017-02-02T17:13:47.207

Do we write our own implementation of the binary tree object for our code? Are the characters of that counted? – xnor – 2014-06-27T20:19:12.217

@xnor Yes, you have to – None – 2014-06-27T20:39:59.553

Are the binary trees complete? – Joshua Taylor – 2014-06-27T21:36:17.620

@JoshuaTaylor not necessarily – None – 2014-06-27T22:20:19.403

I dont like the first limit. Thay will disqualify functional style solutions. – Ray – 2014-06-29T18:53:36.450

Removed rule 1: now it's a totally different challenge – edc65 – 2014-06-30T17:30:10.560

@edc65 I removed it because of what Ray said, I'm not really sure what to do in this situation – None – 2014-06-30T21:26:41.760

1You 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. – edc65 – 2014-06-30T21:51:35.073

2

# 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):
"""
next: next node for the tail node to connect
"""
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.

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 – Alexey – 2015-03-16T11:24:05.463

1

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


1

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

1

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