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.

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.

user26458

Posted 2014-06-27T20:00:50.757

Reputation:

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

Answers

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):
    """
    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.

Ray

Posted 2014-06-27T20:00:50.757

Reputation: 1 946

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

rdans

Posted 2014-06-27T20:00:50.757

Reputation: 995

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

thi gg

Posted 2014-06-27T20:00:50.757

Reputation: 129

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.

millinon

Posted 2014-06-27T20:00:50.757

Reputation: 590

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

Ray

Posted 2014-06-27T20:00:50.757

Reputation: 1 946