The recurrence I have is
$T(n) = 2T(\sqrt{n-1} + 2) + 1$
I don't know how to solve it. I didn't find much on the internet with square roots in recurrences especially with constants inside of it. I'm supposed to find the height of the tree but I have no idea how.
I need to solve this recurrence only using trees. And I can't find anything about solving recurrences with trees and square roots as parameters.
You could try upper and lower bounding the work done in your recurrence tree by two other simpler recurrences.
For instance, this is the function/rate by which your recurrence input decreases at each level: $$f(n) = \sqrt{n-1} + 2$$
We can find a function the decreases faster, for example
$$f_1(n) = \sqrt{n} \leq \sqrt{n-1} + 2 = f(n) \quad \forall n \geq 4$$
We can also find a function that decreases slower, for example
$$f_2(n) = 2\sqrt{n} \geq \sqrt{n-1} + 2 = f(n) \quad \forall n \geq 4$$
Thus with $f_1(n) \leq f(n) \leq f_2(n)$ we can construct two other recurrences based on these new functions:
$$\begin{align*} T_1(n) & = 2T_1(\sqrt{n}) + 1\\ T_2(n) & = 2T_2(2\sqrt{n}) + 1\\ \end{align*}$$
We can then bound our original recurrence by these:
$$T_1(n) \leq T(n) \leq T_2(n)$$
So if you can solve these recurrences, then you can bound $T(n)$ appropriately, because these will lower bound and upper bound the depth of the recursion tree respectively.
I wanted to work through this a bit further for my own satisfaction. Not quite a recursion tree analysis, but I think this function is interesting so I worked through it.
The first $T_1$ we can solve relatively easily with a domain transform:
$$\begin{align*} T_1(n) & = 2T_1(\sqrt{n}) + 1\\ T_1(2^{2^k}) & = 2T_1(2^{2^{k-1}}) + 1\\ S(k) & = 2S(k-1) + 1\\ & = \Theta(2^k)\\ T_1(n) & = \Theta(2^{\log \log n})\\ & = \Theta(\log n) \end{align*}$$
The second $T_2$ is a little trickier, but not much. Let's unwrap this a bit:
$$\begin{align*} T_2(n) &= 2T_2(2\sqrt{n}) + 1\\ &= 2\left(2T_2(2\sqrt{2\sqrt{n}}) + 1\right) + 1\\ &= 4T_2(2^{3/2} \cdot n^{1/4}) + 3\\ &= 4\left(2T_2(2 \cdot (2^{3/2} \cdot n^{1/4})^{1/2}) + 1\right) + 3\\ &= 8T_2(2^{7/4} \cdot n^{1/8}) + 7\\ &= \vdots \end{align*}$$ The pattern starts to emerge and we can perform another domain transform (obviously, to be formal you should prove that the pattern holds by induction, but I'm omitting that).
Let $n = 4^{2^k + 1}$ and when we apply $2 \sqrt{n}$ we get:
$$\begin{align*} 2 \sqrt{4^{2^k + 1}} & = 2 \sqrt{4} \sqrt{4^{2^k}}\\ & = 4 \cdot 4^{2^{k-1}}\\ & = 4^{2^{k-1} + 1} \end{align*}$$
Now with this we do the domain transform: $$\begin{align*} T_2(n) & = 2 T_2(2 \sqrt{n}) + 1 \\ T_2(4^{2^k + 1}) & = 2 T_2( 2 \sqrt{4^{2^k + 1}}) + 1\\ S(k) & = 2 S(k-1) + 1\\ & = \Theta(2^k)\\ T_2(n) & = \Theta(2^{\log_2(\log_4(n) - 1)})\\ & = \Theta(\log n) \end{align*}$$
With this we see:
$$\begin{align*} T_1(n) &\leq T(n) \leq T_2(n) & \forall n \geq 4\\ c_1 \log n &\leq T(n) \leq c_2 \log n & \forall n \geq 4\\ \implies T(n) & = \Theta(\log n) \end{align*}$$
This is not a full solution, but should get you going with what dkaeae commented above (link here).
First thing that is reasonable to try is setting $n = 2^{2^k} + 1$. However, after applying the $f(n) = \sqrt{n - 1} + 2$ in the recurrence, we get $2^{2^{k-1}} + 2$ which is not going to work for our function $g(k)$ as seen in the domain transform scheme.
Next thing that I did, was determine the base case. You can see 1, 2, and 3 will not work. Thus, we have 4 is the first value where the first application of $f^{-1}$ is increasing. We can get the following sequence after repeatedly applying $f^{-1}$:
$$\{4,\ 5,\ 10,\ 65,\ 3970,\ 15745025,\ 247905749270530,\ \ldots\}$$
What we want is a function $g(k)$ equivalent to the $k$th term in this sequence. However, plugging this sequence into OEIS or wolframalpha.com presents no results. From there I tried to see what repeated application of the function $f(n)$ actually did:
$$\begin{align*} f(n) & = \sqrt{n - 1} + 2\\ f(f(n)) & = \sqrt{\sqrt{n - 1} + 1} + 2\\ f^{(3)}(n) & = \sqrt{\sqrt{\sqrt{n - 1} + 1} + 1} + 2\\ f^{(4)}(n) & = \sqrt{\sqrt{\sqrt{\sqrt{n - 1} + 1} + 1} + 1} + 2\\ \vdots & = \vdots \end{align*}$$
The thing to notice here is that each term we have has 2 added on to the end of it. If we can find a function $h(k)$ that fits $f^{(k)}(n) - 2$, then we know $g(k) = h(k) + 2$. Thus, we are now searching for the sequence above, minus 2!
$$\{2,\ 3,\ 8,\ 63,\ 3968,\ 15745023,\ 247905749270528,\ \ldots\}$$
Now when you search this sequence, something does actually turn up. See sequence A003096 from OEIS. Fortunately, there is a closed form (albeit disgusting) for this sequence.
$$h(k) = \lceil c^{2^k}\rceil \quad \text{where } c=1.2955535361865325413981559700593353\ldots $$
Disclaimer: I have no idea how this constant is derived, but this closed form will work for you.
We now know a $g(k) = h(k) + 2 = \lceil c^{2^k}\rceil + 2$. Now try this $g(k)$ with Domain Transform and you should be good to go to apply recursion tree analysis on the transformed domain.
This method will work, but I think the easier way would probably be to upper bound and lower bound the depth of the recursion tree with an easier function.
