How to solve recurrence of a binary tree
There are several slightly different ways of defining binary trees. You seem to be using the following: a binary tree is either a leaf, or an ordered pair of binary trees.
Your recursive procedure actually computes two different functions: the first output is a Boolean function $b$ which measures whether the tree is balanced, and the second is an integer-valued function $h$ which computes the height of the tree.
The height function $h$ is defined as follows: if $T$ is a leaf then $h(T) = 0$, and if $T = (T_\ell,T_r)$ then $h(T) = 1 + \max(h(T_\ell),h(T_r))$. This function computes the height of the tree.
The balancedness function $b$ is defined as follows: if $T$ is a leaf then $b(T) = \mathsf{true}$, and if $T = (T_\ell,T_r)$ then $b(T) = b(T_\ell) \land b(T_r) \land |h(T_\ell) - h(T_r)| \leq 1$. In words, a tree is balanced if in every internal note $v$, the heights of the left and right subtrees differ by at most one.
As you can see, the argument of both functions is a tree.
Your recurrence describes the worst-case running time of the procedure as a function of the number of nodes. The base case is $T(1) = O(1)$ (when the tree is a leaf), and when $n &gt; 1$,
$$ T(n) = \max_{\substack{n_\ell,n_r \geq 1 \\ n_\ell+n_r+1=n}} T(n_\ell) + T(n_r) + O(1). $$
The solution is $T(n) = \Theta(n)$. You can prove this by induction. In particular, if you replace $O(1)$ by $1$, a simple induction shows that $T(n) = n$.
In fact, it is not hard to check that your procedure has running time $\Theta(n)$ on any tree having $n$ nodes, since the recursive calls &quot;visit&quot; every node in the tree, and do $O(1)$ processing per node.