How to save a value to increment in a recursive function (Javascript)

Question

var count = 0;
var NumbOfNodes = function(root){

   if(root.left != null){
       NumbOfNodes(root.left);
   }

   count++;

   if(root.right != null){
       NumbOfNodes(root.right);
   }

   return count;
}

So I have this function that counts the number of nodes in a tree. It is a recursive function. When I make count a global variable, the function works and returns a proper value. The problem is, I want count to be part of the function. But if I declare count inside the function, it keeps on getting reset and I wont get a proper answer fro the function.

So, is there a way to preserve the value of a variable inside a recursive function. This question can help me in many other coding practices.

What I want (Diagram): Tree --> NumbOfNodes() --> gives me the number of nodes. But I don't want to make a global variable just for it.

Thanks!

Answer 1

Just return the count from within the recursion:

var NumbOfNodes = function(root) {
    var count = 0;
    if (root.left != null) {
        count += NumbOfNodes(root.left);
    }

    count++;     // count ourself

    if (root.right != null) {
        count += NumbOfNodes(root.right);
    }

    return count;
}

The basic idea here is that, at each step of the recursion, we start with a count of zero. Then we add to that count the number of nodes in the left and right subtrees, and we add one, to count ourself.

Answer 2

do you really need an extra variable to maintain count?

try this,

var NumbOfNodes = function(root){
   if(!root){
    return 0;
   }   
   return NumbOfNodes(root.right) + NumbOfNodes(root.left) + 1; 
}