# A binary tree question(java)

1. Feb 17, 2008

### transgalactic

there is a given binary tree
each of member are of a Node type
Code (Text):

class Node {
int info;
Node left;
Node right;
}

in the info part of each node we have a number.
in each one of his leaves we have some number
and in each one of its roots (crossroads) we have zeros.

my gole is to build a method which calculates the difference between the
sums of the leaves in the right subtree of T
and the sum of the leaves in the left subtree of T

2. Feb 19, 2008

### malawi_glenn

just visit all nodes in left sub-tree, if both Node.left && Node.right == null, increase the number of leaves.
Then visit right-subtree and do the same.

3. Feb 20, 2008

### transgalactic

what do you meen increase the number of leaves
i need to count them i cant add another object

4. Feb 20, 2008

### Eus

Hi Ho!

A recursive algorithm will nicely solve this.
The idea is that we know that the base case will be when a node is a leaf. In this case the height difference will be just 0.
If it is not a base case, simply solve the problem recursively by traversing the left child and the right child.

Here is the code if you do not want to think about how to implement such a solution.

Code (Text):

int calculate_height_difference (Node node)
{
if (node.left == null && node.right == null)
{
return 0;
}

return calculate_height_difference (node.right) - calculate_height_difference (node.left);
}

Best regards,
Eus

Last edited: Feb 20, 2008
5. Feb 20, 2008

### malawi_glenn

I meant increase the number of leaves VISTIED.

6. Feb 23, 2008

### alphachapmtl

comment

>> what do you meen increase the number of leaves

It means you have reached a leave, so count it by increasing the leaf_count

7. Feb 23, 2008

### malawi_glenn

yes but a recrusive method is better.

class TreeNode{

Object data;
TreeNode left;
TreeNode right;

constructor...

}

class Tree{

.. other methods..

----------------

So you first have a general method like:

diffLeftRight(){

}

numberOfLeaves(TreeNode tr){

if(tr == null)
return 0;
else if(tr.left == null && tr.right == null)
return 1;
else if(tr.left == null && tr.right != null)
return numberOfLeaves(tr.left);
else if(tr.left != null && tr.right == null)
return numberOfLeaves(tr.right);
else
return numberOfLeaves(tr.left) + numberOfLeaves(tr.right);

}

Maybe you need to modify it a bit, but this is the general idea of recursion
}