Hola.
Usando en estos casos n como la cantidad de nodos del árbol binario, las recurrencias cuando el árbol no es vacío vincularían a T(i) y T(n-1-i), donde i es un valor entre 0 y n-1 (considerando que un subárbol tiene i nodos y el otro n-1-i).
Se puede demostrar luego por inducción que T(n) <= cte . n, para alguna contante n0 tal que n >= n0.
En estos casos también se podría justificar que para analizar el peor caso uno puede considerar directamente el caso cuando i=0 (árbol degenerado). Esto es, quedaría esencialmente T(n-1) en la recurrencia, que al igual que el factorial visto en el teórico, nos da O(n).
Si quedan más dudas, sugiero discutirlo en las clases de práctico de esta semana.
Saludos, Carlos