# asymptotics – How to solve recurrence of a binary tree

I’m trying to solve this recurrence of a function of the height of a binary tree with a recursive tree.But I can’t find any pattern to solve it.

$$n_l$$ is the height of the left subtree, $$n_r$$ is the height of the right subtree and $$n$$ is the height of the tree.

$$T(n) = begin{cases} T(n_l)+T(n_r) + 1 & text{if } n ge 0, \ 1 & text{otherwise.}\ end{cases} \ text{Given that }n_l+n_r+1=n$$