# Depth of a Binary Search Tree

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?

• I think this question seems more suitable for the 'stackoverflow' website. – Paul Apr 16 '12 at 5:54
• @Paul: This is a definite gray area. Algorithm-type questions are suitable for scicomp.SE. This isn't really a code-specific question, so it's probably OK here. – aeismail Apr 16 '12 at 6:44
• @aeismail: "Can anyone tell me where is my error?" sounds like debugging to me. – Deathbreath Apr 16 '12 at 22:54

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.

• but this works for Binary Search Trees?? What happen if a node has no childs?? why return + 1 ?? (Sorry for all tihs questions, is just that I am new with binary Search trees and recursion) – Shariff Apr 16 '12 at 14:19
• A binary tree is a binary tree, regardless of whether it is binary or not. And yes, Bernardo's implementation is correct, while also having the benefit of being much easier to read. – Aron Ahmadia Apr 16 '12 at 14:27
• Wow, This is a simple and good algorithm :) is just that I want to knew the level of each node because I want to do a function that checks if the binary tree is balanced, using the property that for each node n in the tree their 2 subtrees have difereence in depth of 0 or 1. @AronAhmadia: How I can use the algorithm by Bernardo to implement this?? – Shariff Apr 16 '12 at 14:57
• Sorry Shariff, but you need to work on this on your own. We are not going to do your homework for you. – Aron Ahmadia Apr 16 '12 at 17:00

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.

• you mean: int auxDepth(int counter, Bin Node Pointer) ? – Shariff Apr 16 '12 at 14:21
• It looks like working... why? – Shariff Apr 16 '12 at 14:21