How to Calculate Leaf Node Difference in a Binary Tree Using Recursion?

[transgalactic]

there is a given binary tree
each of member are of a Node type

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

 

[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.

 

[transgalactic]

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

 

[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.

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);
}

Eus

 

[malawi_glenn]

I meant increase the number of leaves VISTIED.

 

[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

 

[malawi_glenn]

yes but a recrusive method is better.

If your classes are:

class TreeNode{

Object data;
TreeNode left;
TreeNode right;

constructor...

}


class Tree{

TreeNode head;

.. other methods..

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

So you first have a general method like:

diffLeftRight(){

return Math.abs(numberOfLeaves(head.left) - numberOfLeaves(head.right);

}


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
}