What is the complexity of these tree-based algorithms?
Apply the master theorem.

The first algorithm takes $O(N^2)$ time because your underlying recurrence is 

\[ T(N) = 2T(N/2) + N^2 \] 

The second algorithm takes $N\log^2N$ time as you mention. If your work per node is as indicated (and is tight) then this bound is tight as well. 

Update: as commenters point out, the assumption here is that the tree is weight-balanced: each child has half the nodes of the parent. This would imply the log N height bound you indicate, but is not implied by it.