1

I have a Node class as follows:

public class Node {

    private int value;
    private Node leftNode;
    private Node rightNode;

    public Node(Node leftNode, Node rightNode, int value){
        this.leftNode = leftNode;
        this.rightNode = rightNode;
        this.value = value;
    }

   //Getter and Setter methods for these variables are defined here
}

This Node class is used to create a Binary tree. I am writing a recursive function in JAVA to calculate the average of all the nodes. The code I have written below does not give correct answer. I think this is because the values of the parameters average and nodeCount are passed, and not the references. 

public double treeAverage(Node node, double average, int nodeCount){

    nodeCount ++;
    if(node == null) return Double.MAX_VALUE;
    if(node.getLeftNode()==null && node.getRightNode()==null){
        average = ( average + node.getValue() )/nodeCount;
    }

    if(node.getLeftNode()!=null){
        average = treeAverage(node.getLeftNode(), average, nodeCount); 
    }
    if(node.getRightNode()!=null){
        average = treeAverage(node.getRightNode(), average, nodeCount);
    }

    return average;

}

What would be a correct way to right this recursive function in Java? (in C I can pass the references to those parameters). Please correct me if I am wrong.

Improve this question

5 Answers 5

Reset to default
3

I guess you could use a helper method. Something like this (I haven't compiled this code, should be taken as hint)

private static long count = 0L;
private static long sum = 0L;


public static int treeAverageHelper(Node node){

    if(node == null) return 0;
    count ++;
    return node.val + treeAverageHelper(node.left) + treeAverageHelper(node.right);
}

public static double treeAvg(Node n){
    sum = treeAverageHelper(n);
    if (count == 0)
        return 0D;
    else
        return (double)sum/count;
}

The helper, goes through the tree aggregating and counting. And finally you divide the two.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

The use of static scares me, but the idea and intent is pretty spot-on.
+1 yeah, I started with typing static methods, and then I thought, oops, I need a variable. And I added. It's definitely a bad idea -- not thread safe. But I wasn't initially planning to solve the problem. It happen to be almost complete solution. Thanks for pointing out.
This works but I think if I have a different class having these functions, then the values of sum and count would persist between different objects :) so probably not a goood idea? I think @makoto's solution of moving the variables to a higher scope seems pretty good, but even here I have to manually reset these variables before I return the average, so that the values don't persist between calls to the same function made by the same object of this class. (Correct me if I am wrong!)
well, this is just a hint to point out what the mistake in your perception of the algorithm was. :) The implementation, null checks, resets -- I left to you to sort out. I central idea is bend your mind to think towards splitting the problem into 2 parts: aggregation, and average computation. Which, as your question says, was the hardest part for you. I guess (seeing your answer), I was able to do that. It's up to you to choose the appropriate answer.
@rgamber "different class having these functions" - you probably meant to say: "different objects having these functions", and in such a case you can remove all the static declarations and create a separate instance for each tree and the solution will hold. +1
|
2

I'm not a fan of these two parts:

if(node == null) return Double.MAX_VALUE;
if(node.getLeftNode()==null && node.getRightNode()==null){
    average = ( average + node.getValue() )/nodeCount;
}

For the first statement, why would the average of an empty tree be the highest possible Double? Seems arbitrary. It would be simpler to say it doesn't exist, Double.NaN, or even 0.0 - since the tree has zero elements in it.

For the second statement, you have the logic correct in that if both the children are null, you get back its value. However, you're going to be wrecking your average along the way - if you have twelve nodes, and you're on your third, then your average values will be different when you move to your fourth node.

Move nodeCount to a higher scope, and don't worry about computing the actual average until you've counted the sum of all nodes from the recursive call. Lastly, pass along the total sum of your nodes as you go along.

Improve this answer

4 Comments

Thanks for the explanation. Double.NaN makes more sense. However, I am not sure I understood your last paragraph. By a higherscope, do you mean a wrapper function?
You could use a wrapper function, but I was thinking a bit simpler - class scope variable.
I would really appreciate if you can put up some sample code. I don't want to get it right anyhow and just make it work. I am trying to understand recursive functions.
based on your suggestion I have added a solution which works. It'llbe awesome if you can take a peek and let me know if that's what you meant. Thanks!
2

I think there is a problem in average calculation. According to your code, if node have no left child and no right child, you added average + node.getValue() and divide this result by nodeCount.

In fact,

average is total value divided by count.

That means you should get total node value first and divide this by nodeCount.

Improve this answer

Comments

0

You need to define a class, such as

class RecursionValues {
     int nodeCount;
     double average;
}

... and then in your recursive call you pass an instance of this class and modify its fields.

Improve this answer

7 Comments

Why would you need to define another class? You have pretty much everything you need to sum the values of this tree with the Node object.
@Makoto actually his suggestion is exactly like yours: a wrapper class (which normally will be called tree) which will record every insert and thus maintain the count and possibly the sum of all nodes and thus will make the average calculation very easy.
@alfasin: I make no reference to any wrapper classes...global variables, wrapper functions? Sure. Classes? Not so much.
@Makoto you say potatoes I say pota'toes, it's basically the same idea: add another level of abstraction. It doesn't really matter how you implement it.
@alfasin: It's not another level of abstraction; you can't get both the sum and average of the tree in one go. I don't even think that a wrapper function would be necessary in this case either.
|
0

This is how I was able to get it working. Please let me know if it is not a good way.

private double sum = 0;
private int nodeCount = 0;

public double treeAverage(Node node){

    if(node == null) return Double.NaN; //Null check

    sum = treeSum(node);
    double average = (sum/nodeCount);

    // before returning, reset the sum and nodeCount, so that same object can use the same function starting with correct/zero values of sum and nodeCount
    sum = 0; nodeCount = 0;

    return average;

}

public double treeSum(Node node){

    nodeCount ++; //update the nodeCount
    sum = sum + node.getValue(); //update the sum to include this node

    /* If the current node has children, recurse*/      
    if(node.getLeftNode()!=null){
        sum = treeSum(node.getLeftNode()); 
    }
    if(node.getRightNode()!=null){
        sum = treeSum(node.getRightNode());
    }

    return sum;

}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.