# Tree list recursion from Stanford tutorial

I have found this appearing-to-be famous problem in Stanford tutorial about trees and decided to solve it.

My solution appears to work great:

 #include <iostream>
using namespace std;

struct num {

int n;
num* left;
num* right;
num* next;
num* pre;
};

num* cr (int data) {

num* node = new num;
node->n = data;
node->left = 0;
node->right = 0;
return node;
}

/* function for tree creation*/
void treecre (num* & node) {

node = cr (10);
node->left = cr (8);
node->left->left = cr (6);
node->left->left->left = cr (4);
node->right = cr (12);
node->right->right = cr (14);
node->right->right->right = cr (16);
node->right->left = cr(11);
node ->left->right = cr (9);
}
// function for transforming the tree into linked list with next and previous // links
// but without linking the first and last element yet
num* btc (num* node, num*& list) {
num* temp1 = 0;
num* max = node;
if (node == 0) return 0;
else {
btc (node->right, list);
num* temp = new num;
temp->n = node->n;
temp ->next = list;
if (list != 0) list->pre = temp;
list = temp;
btc (node->left, list);
}
return list;
}

void printtree (num* node) {
if (node != 0) {
printtree (node->left);
cout << node->n;
printtree (node->right);
}
}
// printing the linked list backwards
void printback (num*& list, int& k) {
if (k < 15) {
cout << list->n;
list = list->pre;
printback (list, ++k);}
else {cout << list->n;}
}
// and in right direction
void printlistto (num*& list, int& k) {
if (k < 12) {
cout << list->n;
list = list->next;
printlistto (list, ++k);
}
else {
cout << list->n; }
}

int main () {
num* node = 0;
num* list = 0;
int k = 0;
treecre (node);
printtree (node);
cout << endl;
list = btc (node, list);
// next lines link the first and last elemets
num* temp1 = list;
if (temp1->next!= 0) {
while (temp1->next != 0) {
temp1 = temp1->next;
}}
temp1->next = list;
list->pre = temp1;

printback (list, k);
cout << endl;
cin.get ();
cin.ignore();
}


But then I take a look at this Stanford solution, which is way longer and uses other tactics.

Could you please tell me if I overlooked something? Does my version have some sufficient drawbacks or if it is fine?

• Should really be re-classified as C. May use some C++ features but the style is definitely not C++ – Martin York Mar 18 '15 at 2:07

Your solution may work great, but I see some room for improvement, especially in terms of readability and maintainability and using OO.

I quickly went over your recursive function btc, it seems to do the trick. But the code is a bit messy.

The stanford solution tries to embrace the typical list methods, like: appending elements, joining lists, etc. In fact that's the goal, right: porting a binary sorted tree to a list, so one should also provide a good list interface. They also do this in a good object oriented/modular and readable way.

A review on your coding style

To start: you miss some indentation (in your if/else clauses). This already can make it more readable! Perhaps also document some steps in the recursion method, since recursion always results to confusion.

Methods

your method names are not that understandable, use camelCase and use appropriate, complete names, that indicate the purpose of the method.

for example:

treecre()


should be

treeCreate()


it would even be better to use a Tree class that has a create() method, which builds your test tree.

Classes

You also used a struct for your node, may I suggest to use classes, since they offer a wide set of feature that can be used for future purposes of your code: inheritance, polymorphism, etc. This is important since one might want to extend this implementation to handle nodes that contain ASCII characters instead of integers. Or, refactor the class to use C++ templates to support generic types.

In addition I would use the standard list/binary tree names, like: root, node, .. which is easier for communication purposes.

I hope this is a bit helpful!