Depth of a Binary Search Tree

Question

I wrote a function to search a Binary Search Tree, but I have logic problems: When I insert some values, and I have a tree of 2 levels, and the final level (2 in this case) is not full (full is that it does not have all child nodes) it returns 3, not 2:

// --- Definition of depth()
template<typename DataType>
int BST<DataType>::depth()
{

  int counter = 0; 

  return Auxdepth(counter, myRoot);

}


// --- Definition of Auxdepth()
template<typename Datatype>
int BST<Datatype>::Auxdepth(int &counter, BinNodePointer subtree)
{
 //BinNodePointer parameter is myRoot, which is the root node
int a;
int b; 

if(empty()) return -1;// garbage value

if(subtree->left == 0 && subtree->right == 0)
    return counter;

else if(subtree->left == 0){
    int x = counter++;
    a= Auxdepth(x,subtree->right);
    return a;
}

else if(subtree->right == 0){
    int x = counter++;
    a = Auxdepth(x,subtree->left);
    return a;
}

if(subtree != 0) { // Recursion
    int x = counter + 1;
    cout << "This is x " << x << endl;
    a = Auxdepth(x, subtree->left);
    b = Auxdepth(x, subtree->right);

            if(a > b) return a;
            else return b;
    }
} 

Note: The depth function is there just to be more friendly. Can anyone tell me where is my error?

Answer 1

What about this implementation....(the code is C, but you could easily translate to your C++ code).

int depth(Tree *t)
{
  if(t==NULL)
    return -1;
  else
    return 1 + max( depth(t->subleft), depth(t->subright) );
}

I don't know if your version is more efficient, but this one works fine for me.

Answer 2

I'm not sure if this is your problem, but you are passing around counter by reference, and that is surely going to cause errors the way you have implemented things currently. Try switching from a call-by-reference to a call-by-value and returning the value of counter to make a copy.