Dubbio su attraversamento albero binario

[Net_Raider]

salve per esercizio ho scritto un algoritmo ricorsivo che attraversa un albero binario per calcolare la profondità massima dello stesso.

Pseudocodice: 

depth(Tree T)
x = 0; y = 0
if (left(T) != NULL) x = depth(left(T)) + 1
if (right(T) != NULL) y = depth(right(T)) + 1
return max{x, y}

come da traccia ho provato a calcolare la complessità dell'algoritmo:
se $n$ è il numero dei nodi dell'albero e $x$ è un generico nodo dell'albero $ns$ è il numero di nodi nel sottoalbero sinistro di $x$ e $nd$ è il numero di nodi del sottoalbero destro di $x$

$T(n) = T(ns) + T(nd) + \theta(1) = $
$= T(n - 1) + T(n - 1) + \theta(1) =$
$= 2*T(n - 1) + \theta(1)$

ora iterando ottengo (supponiamo $T(1) = 1$):
$T(n) = 2*T(n - 1) + \theta(1)= $
$= 4*T(n - 2) + \theta(1) = $
$= 8*T(n - 3) + \theta(1) = $
$.$
$.$
$.$
$= 2^i*T(n - i) + \theta(1)$
l'algoritmo viene eseguito fin quando $i < n$
ma in questo modo mi esce che il tempo impiegato per scorrere l'albero è esponenziale, quando dovrebbe essere lineare. dov'è che sbaglio???

grazie per l'attenzione.
Saluti

[Net_Raider]

ho risolto, ho risolto:
l'equazione era sbagliata, viene
$T(n) = 2 * T(n/2) + 1$
che iterata viene
$= 2^i * T(n/2^i) + i$
da cui $ i = \logn$
quindi $T(n) = O(n)$