F рекурсивно с возвращением глубины дерева, примерно так:

bool ans = true;
long long lastNum=-2000000000000000000LL;
int f(){
	if (emptyTree()) return 1;
	int left = f();
	int middle = readNumber();
	if (middle<=lastNum){ ans=false; return -1;}
	lastNum=middle;
	int right = f();
	if (abs(left-right)>1){ ans=false; return -1;
	return max(left,right)+1;
}