Premature return from recursion stack

[qwerty1989]

I wrote a code for detecting if a given binary tree is a Binary search tree.

I have the following in the recursion:

int check_BST(node** tree)
{

     //conditions for NULL pointer termination specified here....

     if(/*conditions for binary search tree is true*/)

              return 1*checkBST(*tree->left)*checkBST(*tree->right);

     else

              return 0;
}

Now, as you see from the logic, say I am in an internal node and find that it returns 0, then I may very well exit from the whole recursion stack without having to return the values recursively. Is there any provision in the language for this or a means which can facilitate this ?

[Athar]

Change the return value to bool and perform the following change:

return checkBST(*tree->left) && checkBST(*tree->right);

There are also exceptions that could be used to unwind the stack, but I don't think that would be a good solution here.

[qwerty1989]

@Athar: The bool thing is fine. I coded this in a C Compiler and that is why I did not use the bool.

My real question is if there is any facility by which I can directly return to the initial program in the stack without having to return to each and every calling function. In huge trees, I can potentially save up on a lot of calculations, if I prematurely return from the stack.

[rollie]

Have you tried performing the search iteratively? I can't recall an algorithm for this off the top, but something like the below should work (I think?):

int check_BST(node** tree)
{

	//conditions for NULL pointer termination specified here....
	std::list<node**> Nodes;
	Nodes.push_back(tree);
	std::list<node**>::iterator itr = Nodes.begin();
	do
	{
		if(/* NOT conditions for binary search tree is true*/)
		{
			return 0;
		}
		Nodes.push_back(*tree->left);
		Nodes.push_back(*tree->right);
	} while (++itr != Nodes.end());
}

--Rollie

[qwerty1989]

Yes. An iterative approach is possible. But I asked this question only because in previous recursion problems I have not really come across such a situation. It was more curiosity than necessity that made me post this :D

[RedX]

There are no such facilities in the specification of c++. You could save the current esp by doing

void bla(){
unsigned int cur_esp = &cur_esp;
// cur_esp now contains esp address
}

then you could, with assembler, try to jump to that adress and doing a ret, but you'd have to pay attention to popping the flags and restoring registers that were stored when you went down deeper in the recursion.

[Athar]

In huge trees, I can potentially save up on a lot of calculations, if I prematurely return from the stack.

Not really, how often you have to return only depends on the current tree depth, which should always be fairly low, no matter how huge the tree.
Please note that && doesn't execute the second operand if the first one is false. This is why the solution I posted doesn't check the rest of the tree once an invalid node has been found.

[helios]

jump to that adress and doing a ret, but you'd have to pay attention to popping the flags and restoring registers that were stored when you went down deeper in the recursion.

Yeah! Nothing like ugly hacks that are unportable, make assumptions on calling conventions, are bound to break at the first compiler optimization, and save mere cycles!

Short-circuit evaluation is the way to go, here. Note that the expression Athar posted earlier works even if checkBST() returns a non-bool integer, as long as it returns zero when it means to return false, and anything else when it means to return true.