Binary tree algorithm asymptotic analysis problem

Question

Assume we have a perfectly balanced Binary tree. We have the following algorithm: For each passed node, traverse through all its ancestors and then do the same algorithm for the left and right child of the node.

So, the way I try to find the Big-O complexity is this: There are O(N) nodes in the tree and each has O(log2N) ancestors, so overall we'll have O(N*log2N) complexity if we start the algorithm from the root.

Now consider another problem for the same Binary tree: For each node, go to its left and right child. If the node doesn't have any children, for each ancestor, go through all the previous ancestors.

Now my attempt for finding the complexity: We basically keep going through every node until we reach the leafs. There are N/2 leafs in a perfect Binary tree with N nodes and for each leaf we have (log2N) ancestors. Since for each ancestor we have to traverse every previous, the overal compexity when we're on a leaf is O(Log2(N)^2), so overall complexity becomes O(N*log2(N)^2).

The problem is that I think the algorithms basically do the same thing. Why do I get different complexities for them?

Answer 1

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.