Finding a tree successor with a given key

[qq387]

I am trying to write a function that will return the next smallest element key greater than the parameter q when called in a binary balanced tree The code works fine up to the point when no values greater than q is found in the first parts of left nodes of the tree,which means that I have to go check the nodes on the right and the test code gives me the following, I don't understand which part has gone wrong.

Prepared trees; now start test1
next larger key after 10 should be 12, instead found 131075
next larger key after 20 should be 22, instead found 131075
next larger key after 30 should be 32, instead found 131075
next larger key after 60 should be 62, instead found 131075
next larger key after 70 should be 72, instead found 131075
Press any key to continue . . .

  int find_next_larger(tree_node_t *tree, int q)
{
	//return base null tree
	if (tree->left == NULL)
		return q;
	else
	{
		tree_node_t * tmp_node;
		tree_node_t * right_node_of_path[10000];
		int i = 0;
		tmp_node = tree;

		//if the tree has right node, run through the entire tree starting from left
		while (tmp_node->right != NULL)
		{
			right_node_of_path[i] = tmp_node;
			i++;
			if (q < tmp_node->key)
			{
				tmp_node = tmp_node->left;
			}
			else
			{
				tmp_node = tmp_node->right;
			}

		}

		if (tmp_node->key > q)
			return tmp_node->key;
		else
		{
			while (i >= 0)
			{
				tmp_node = right_node_of_path[i];
				i--;
			}
			tmp_node = tmp_node->right;
			while (tmp_node->right != NULL)
				tmp_node = tmp_node->left;

			return tmp_node->key;
		}
	}

}

[leryss22]

This implementation doesnt look really efficient here I have made you a quick recursive implementation using a DFS postorder traversal.

class node {
public:
	int			mValue;
	node*		mLeft;
	node*		mRight;
};


class tree {
public:
	tree() { mRoot = NULL; };
private:
	node* mRoot;
};

int min(int a, int b) {
	return (a < b) ? a : b;
}

int findNextLarger(node* it, int key) {
	//static means it has a static value over all the recursive calls
	//(~(1 << 31)) this gets the maximum int value
	static int max = ~(1 << 31);

	//if the node exists
	if (it != NULL) {
		//if its a leaf node then we can return the value of it
		//if its less than the key we just return the biggest possible number
		if (it->mLeft == NULL && it->mRight == NULL) {
			if (it->mValue > key)
				return it->mValue;
			else
				return max;
		}
		else
			return min(findNextLarger(it->mLeft, key), findNextLarger(it->mRight, key));
	}
}

the disadvantage with this code is that if no value is bigger than the key the function will return the maximum value of an int
anyway you can tweak this