Binary tree algorithm asymptotic analysis problem
They're not the same thing.  Consider some node $x$.  Ask yourself how many times the algorithm does the operation "iterate through all the ancestors of $x$".

The first algorithm does this operation once.  The second algorithm does this operation $k$ times, where $k$ is the number of descendants of $x$.  So, it's no surprise that the second algorithm takes longer: it's doing a lot more repeated work.