binary search tree

[zio_mangrovia]

I need help because I'm not able to write code for this exercise:

I have binary search tree where every node has label of integer type.
Node is said even (odd) type if its label is even (odd).
For every node X, which is not leaf, It's defined D as maximum distance among X and one of its leaves of the same type.
If subtree X doesn't contain any leaves of the same type, D=-1.
It's necessary to write code for procedure with complexity at maximum O(n) to calculate D for every node, which is not a leaf.

i tried several times unsuccessfully.

[VictorN]

I need help because I'm not able to write code for this exercise:
...
i tried several times unsuccessfully.

And how did you try it? And what went wrong?

[zio_mangrovia]

And how did you try it? And what went wrong?

I don't find to think the way using recursion to keep track of node type to compare, for example, to every leaf (which are at several levels)
I think It's easy if I have to calculate this Properties only for father of every leaf but not for the other top nodes

[wolle]

1. The tree is recursively traversed once.

2. Whenever a leaf is reached a return record R is filled in. It's then passed down when the recursion winds back toward the root.

3. The return record initially looks like this,

struct R {
   int odd = -1;
   int even = -1;
};

The odd and the even numbers indicate distance D for each type. -1 means no distance exists yet.

4. At an odd leaf the record is set to,

struct  R {
   int odd = 0; // 0 distance so far
   int even = -1; // no distance exists
};

At an even leaf it's the other way around, even is set to 0 and odd to -1.

5. When a parent node is reached the records from the children are updated and merged. How to do it requires some thinking on your part! Then the D of the node is set based on the info in the merged record. It also requires some thinking. Finally the merged record is returned (to the parent thanks to the recursion winding back).

6. After one tree traversal all D have been set which indicates O(N) complexity.

[zio_mangrovia]

...

When a parent node is reached the records from the children are updated and merged. How to do it requires some thinking on your part! Then the D of the node is set based on the info in the merged record. It also requires some thinking. Finally the merged record is returned (to the parent thanks to the recursion winding back).

you can't imagine how much you helped me to understand problem.
I thought to this procedure and it Works.... after 2 daysssss

struct node {					// D is max dist. from node to leaf of same type
	int label;					// -1 means there is no leaf of same type of node
	int D;					
	int leaf;                                     // leaf is flag, 1: leaf 0: not leaf 
	node *left, *right;		
	node(int inf): label(inf), D(-1), leaf(0), left(NULL), right(NULL) {};
};

struct leafstate {
	int even_sx;
	int even_dx;
	int odd_sx;
	int odd_dx;
	leafstate(): even_sx(-1), even_dx(-1), odd_sx(-1), odd_dx(-1) {};
};

vector<int> final;

void calcolaD(node *tree, int &even, int &odd) {
	leafstate lf;
	if (!tree)
		return;
	if (tree && !tree->left && !tree->right && tree->label%2==0) { // even leaf
		tree->leaf=1;
		++even;
		return;
	}
	if (tree && !tree->left && !tree->right && tree->label%2==1) { // odd leaf
		tree->leaf=1;
		++odd;
		return;
	}
	calcolaD(tree->left, lf.even_sx, lf.odd_sx);		// get even-odd values
	calcolaD(tree->right, lf.even_dx, lf.odd_dx);	// from sons
	if ( lf.odd_dx != -1 )
		++(lf.odd_dx);
	if ( lf.even_dx != -1 )
		++(lf.even_dx);
	if ( lf.odd_sx != -1 )
		++(lf.odd_sx);
	if ( lf.even_sx != -1 )
		++(lf.even_sx);
	even = max(lf.even_sx, lf.even_dx);
	odd = max(lf.odd_sx, lf.odd_dx);

	if ( tree->label%2 == 0 )
		tree->D = even;
	else 
		tree->D = odd;
	if (!tree->leaf)
		final.push_back(tree->D);     // I put values into vector, excluded leaves, because It's required by problem.
}

int main() {
	node* abr = NULL;
	int e, o;
	e = o = -1;
	if ( abr )
            calcolaD(abr, e, o);
}

What do you think?

[zio_mangrovia]

final.push_back(tree->D);

This statement doesn't change algorithm complexity, right? It's O(1), right?

[wolle]

This statement doesn't change algorithm complexity, right? It's O(1), right?

You're right. Adding something at the end of an std::vector is an O(1) operation (*) so this won't change the overall O(N) complexity of the algorithm even if you do it each time you have a new D.

Just a remark. There's a slightly different way of doing it and that's to make a function out of calcolaD. It would look like this,

struct leafstate { 
	int even;
	int odd;
	leafstate(): even(-1), odd(-1) {};
};

leafstate calcolaD(node *tree); // signature

So instead of returning values as output parameters int &even and int &odd you return these values by way of returning the leafstate struct as a calcolaD function value instead.

This will make your code look somewhat cleaner and simpler and it would be more in line with what is generally expected. If it's a graded exercise I suppose it will improve your chances of getting a high grade especially if your professors are traditionalists.

(*) But this O(1) is on average (or amortized as it's also called). If you have reason to believe this distinction matters it's safest to break the collection of the D values out of calcolaD and do it in a separate function which traverses the tree once more. Then calcolaD itself will be solid O(N).

[zio_mangrovia]

This will make your code look somewhat cleaner and simpler and it would be more in line with what is generally expected. If it's a graded exercise I suppose it will improve your chances of getting a high grade especially if your professors are traditionalists.

Good idea, I'll try again to write code according to your suggestion.
Thanks