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