Zok - 5 months ago 37

Java Question

I am trying to assign numbers to each leaf in a tree.

For example if we have a tree that has 6 leaves, I want the leaves to have the numbers from 0 to 5.

I don't know why my code doesn't work well, I have been trying many times even in recursive ways but it seems I am missing something..

`public class Node {`

int index;

int id;

Node left;

Node right;

// Constructor and setters/getters.

public static void num(Node n) {

int ini=0;

if(n==null)

{

}

if(n.isLeaf())

{

n.index=ini;

ini++;

}

if(!n.isLeaf())

{

num(n.getleft());

num(n.getRight());

}

}

Also I wanted to get the number of the leaves in the tree.

For example, Our tree looks like

`1`

/ \

2 3

/ \ / \

6 9 8 10

/

4

public static int numberChild(Node n, int count)

{

if (n == null) {

return 0;

}

if (n.getleft() == null && n.getRight() == null) {

return 1 + count;

} else {

int lc = numberChild(n.getleft(), count);

int rc = numberChild(n.getRight(), lc);

return rc;

}

}

will give me a wrong number of leaves, 2 instead of 4 !

Any Help ?

Answer

If `n == null`

you return 0. You should return `count`

or your previous count gets lost. In your example when counting leaves for the 6 node, you correctly get 1 from the 4 node below it. Then you call `numberChild()`

for the non-existing right child, it returns 0, so the count you return for the 6 node is 0, not 1.

Edit: To assign values to the leaves I believe you should use the same idea that you use for counting the nodes, pass a count to the recursive method so it knows how many leaves have already been numbered to the left of the current node, and return an updated count. You `num`

method will be like another version of your `numberChild`

method, extended with the assignment of new indices to the leaf nodes.