CODEWITHSUNDEEP
crecursion
user3131972
user3131972

Reputation: 13

Strange behavior of a recursive function

This function must count the number of nodes in a binary tree. Tree contains more than 1000 nodes, and the number of recursive calls supposedly to be the same, but the value of the variable 'count' is not greater than 10. Why? What i am doing wrong?

int tree_depth(BST_T *tree) {
    static int count;
    count++;
    if(tree->left!=NULL) tree_depth(tree->left);
    else if(tree->right!=NULL) tree_depth(tree->right);
    return count;
}

Upvotes: 1

Views: 132

Answers (3)

David R Tribble
David R Tribble

Reputation: 12214

Summing up the comments, your main problem is the else. Getting rid of it will allow the code to count both branches of every subtree.

Another problem is that it's generally considered bad practice to use a static variable for things like this. Why not just have each call return the count of nodes in the subtree it is passed? That way your code is thread-safe, more correct, and just plain simpler:

int tree_depth(const BST_T *tree)
{
    int  count = 1;

    if (tree == NULL)
        return 0;
    if (tree->left != NULL)
        count += tree_depth(tree->left);
    if (tree->right != NULL)
        count += tree_depth(tree->right);
    return count;
}

I've also added a const to the tree, since you're not modifying the tree in any way, only reading it.

Also be aware that a pathological tree (i.e., one with all null left links or all null right links, which is essentially just a linked list instead of a tree tree), will cause N nested calls for a tree having N nodes.

Addendum

Made some corrections to the code above, per some of comments below. I also added an additional check to test whether the tree pointer itself is null.

Also, as @twalberg pointed out, using a static counter will fail on all calls after the first, since it's not re-initialized to zero on each call. Getting rid of it entirely makes the whole thing simpler, and thread-safe as well.

Upvotes: 2

twalberg
twalberg

Reputation: 62499

Here's a slightly different approach:

int tree_depth(const BST_T *tree)
{ if (!tree)
    return 1 + tree_depth(tree -> left) + tree_depth(tree -> left);
  return 0;
}

Except, note that tree_depth is probably a confusing name for this function, as it's more like count_nodes...

Upvotes: 0

tcxbalage
tcxbalage

Reputation: 726

I think you should do something with the return values, otherwise you only receive the first level's count. Try this:

if(tree->left!=NULL) 
  count += tree_depth(tree->left);
else if(tree->right!=NULL) 
  count += tree_depth(tree->right);

Upvotes: -1

Related Questions