Zok Zok - 9 days ago 5
Java Question

Assigning distinct values to leaves in a tree

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.