We were not looking at arbitrary branching trees correctly yersterday. The actual formula for the number of nodes in a 3-branching tree in d-dimensions is:
N3(d) = ( N3(d - 1) - 1 ) * N3(d - 1) + 2 = N3(d - 1)^2 - N3(d - 1) + 2
When solving this recurrence, the largest term becomes N3(d)^(2^d), so this is big-omega(2^(2^d)). Instead of being exponential, it is in fact hyper-exponential.