Returning recursive ternary freaks out
- by David Titarenco
Hi, assume this following function:
int binaryTree::findHeight(node *n) {
if (n == NULL) {
return 0;
} else {
return 1 + max(findHeight(n->left), findHeight(n->right));
}
}
Pretty standard recursive treeHeight function for a given binary search tree binaryTree. Now, I was helping a friend (he's taking an algorithms course), and I ran into some weird issue with this function that I couldn't 100% explain to him.
With max being defined as max(a,b) ((a)>(b)?(a):(b)) (which happens to be the max definition in windef.h), the recursive function freaks out (it runs something like n^n times where n is the tree height). This obviously makes checking the height of a tree with 3000 elements take very, very long.
However, if max is defined via templating, like std does it, everything is okay. So using std::max fixed his problem. I just want to know why.
Also, why does the countLeaves function work fine, using the same programmatic recursion?
int binaryTree::countLeaves(node *n) {
if (n == NULL) {
return 0;
} else if (n->left == NULL && n->right == NULL) {
return 1;
} else {
return countLeaves(n->left) + countLeaves(n->right);
}
}
Is it because in returning the ternary function, the values a => countLeaves(n->left) and b => countLeaves(n->right) were recursively double called simply because they were the resultants?
Thank you!
