How can I solve $T(n) = 2T(\sqrt{n-1} + 2) + 1$ recurrence using tree method?
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) &amp; = 2T_1(\sqrt{n}) + 1\\
T_2(n) &amp; = 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)       &amp; = 2T_1(\sqrt{n}) + 1\\
T_1(2^{2^k}) &amp; = 2T_1(2^{2^{k-1}}) + 1\\
S(k)         &amp; = 2S(k-1) + 1\\
             &amp; = \Theta(2^k)\\
T_1(n)         &amp; = \Theta(2^{\log \log n})\\
             &amp; = \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) &amp;= 2T_2(2\sqrt{n}) + 1\\
       &amp;= 2\left(2T_2(2\sqrt{2\sqrt{n}}) + 1\right) + 1\\
       &amp;= 4T_2(2^{3/2} \cdot n^{1/4}) + 3\\
       &amp;= 4\left(2T_2(2 \cdot (2^{3/2} \cdot n^{1/4})^{1/2}) + 1\right) + 3\\
       &amp;= 8T_2(2^{7/4} \cdot n^{1/8}) + 7\\
       &amp;= \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}} &amp; = 2 \sqrt{4} \sqrt{4^{2^k}}\\
                     &amp; = 4 \cdot 4^{2^{k-1}}\\
                     &amp; = 4^{2^{k-1} + 1}
\end{align*}$$

Now with this we do the domain transform:
$$\begin{align*}
T_2(n) &amp; = 2 T_2(2 \sqrt{n}) + 1 \\
T_2(4^{2^k + 1}) &amp; = 2 T_2( 2 \sqrt{4^{2^k + 1}}) + 1\\
S(k) &amp; = 2 S(k-1) + 1\\
     &amp; = \Theta(2^k)\\
T_2(n) &amp; = \Theta(2^{\log_2(\log_4(n) - 1)})\\
       &amp; = \Theta(\log n)
\end{align*}$$

With this we see:

$$\begin{align*}
T_1(n) &amp;\leq T(n) \leq T_2(n) &amp; \forall n \geq 4\\
c_1 \log n &amp;\leq T(n) \leq c_2 \log n &amp; \forall n \geq 4\\
\implies T(n) &amp; = \Theta(\log n)
\end{align*}$$