Sorry if any of this is confusing, I can do my best to clarify any completed work if necessary. I believe this might be a modification of the Fibonacci recurrence, but I'm unclear on that.
I am trying to solve the recurrence relationship for the given equation, and am suggested to use the recurrence tree method. I am almost certain the actual complexity is $\theta(n^2)$, but I am unable to walk through the full proof. Using this, I expanded the tree to get the following results.
Level 1: $n^2$
Level 2: $n^2/4$ and $n^2/2$
Level 3: $n^2/16$ , $n^2/8$ , $n^2/8$ , $n^2/16$
Level 4: $n^2/64$ , $n^2/32$ , $n^2/32$ , $n^2/16$ , $n^2/64$ , $n^2/32$ , $n^2/32$ , $n^2/16$
and so on...
All the examples in my textbook and online seem to arrive upon a constant growth coefficient in the format
coefficient of growth=x , a=coefficient in front of T(n/b), and b equals the divisor in $T(n/b)$
$T(n) = cn^2 + (x)^1*cn^2 + x^2*cn^2 ... + x^(log_b(n-1))*cn^2 + \theta(n^{log_b(a)})$
What I am confused on is that the recurrence doesn't seem constant. The summation of the rows results in
Level 1: $n^2$
Level 2: $(3/4)n^2$
Level 3: $(6/16)n^2$
Level 4: $(18/64)n^2$
Level 5: $(54/256)n^2$
This can't be put in the form $(x/y)^i$ but rather seems to grow at $3/4$, $3/4*2/4$,$2/4*(3/4)^2$, and $2/4*(3/4)^3$.
Is this a possible recurrence relation, and what height would I sum it over? Is the height $log_2(n)$ or $log_{sqrt(2)}n$? I am assuming the height is based on the n/sqrt(2) as it grows slower, but I am unsure.
Firstly, note that the length of the tree is $\log_{\sqrt{2}}n$ as you rightly pointed out. Secondly, it is difficult to provide a $\Theta(\cdot)$ bound since many of the leaves will be empty (because there are "two trees") and so I will just try to provide an upper bound. Finally, since the cost at each iteration (level) is $O(n^2)$ and assuming that the base case is $T(1) = O(1)$, the recurrence gives, $O(n^2\log_{\sqrt{2}}n)$.
Edit: For a loose lower bound, it is possible to argue that there are at least $\log_2 n$ levels each with complexity $n^2$ and so the lower bound will be $\Omega(n^2\log_2 n)$.