Return to Revisions

You can simplify all those algorithms a lot by just moving the test for NULL to a single location near the top. Then treating left and write identically (even when NULL).

CNode * CNode::findStackBased(int number)
{
 stack<CNode*> onStack;
 onStack.push(this);
 while(!onStack.empty())
 {
 CNode tmp = onStack.top();
 onStack.pop();
 if (!tmp) {
 continue;
 }
 if (tmp->number == number) {
 return tmp;
 }
 onStack.push(tmp->right);
 onStack.push(tmp->left);
 }
 return NULL;
}

Recursion

CNode* CNode::findRecursion(int number) {
 return findRecusion(this, number);
}
CNode* CNode::findRecursion(CNode node, int number) {
 if ((node == NULL) || (node->number == number) {
 return node;
 }
 return findRecursion(node->left); // Only do the right side if left
 || findRecursion(node->right); // returns NULL
}

Walking along the edge just seems to be doing depth first left to right traversal. Its just messy and convoluted. It also requires the concept of a parent pointer.

Each of the above have have some advantages/drawbacks, but performance wise 'walking along the edge is the winner so far(out of the 3 given above).

Really. Please name them.
How are you measuring that? Not convinced that it is actually significantly faster because of all the extra comparisons you are doing. But for certain types of trees it could be faster as you don't need to maintain a stack object.

What you are doing is trading space for time (a common optimization). You are adding a parent pointer into each node to help you do the traversal more quickly. The other two techniques require you to build and maintain a stack (the state of the search (one explicitly and one implicitly in the call stack)) while the walk the edge has the information you need built into the graph.

My question is:

Do you see any way to optimize it further (recursive implementation already benefits from the tail recursion optimization, at least gcc seems to optimize it this way)?

I would be surprised if most compilers don't turn the recursion into a loop. Its an easy optimization. I would worry less about optimization and more about readability. Its usually much more important. The compilers are darn good at making the code fast.