Basically you're asking why the following two functions have the same time complexity in terms of big O (as they're both O(n^m)):
- n^0 + n^1 + n^2 + ... + n^m
- n^m
The reason is that, at some point, for values of n and m the term n^m dwarfs all the other terms of these functions. As the input grows the runtime of the function as a whole will be determined by n^m.
Even if you come up with a function that takes n^m + 1000000000000 then at some point n^m will still be the deciding term in how long it takes to run. In other words, the runtime of both functions is bounded by a function with the term n^m times some constant.
In your example, running tree traversal once at depth m or running it m times up until depth m have the same time complexity because, as the tree grows, the runtime of running at depth m dwarfs all the other runs. Looking at how long it takes to run at depth m is basically all that is needed to find a function that bounds the runtime of both tasks.
To give another example, we can think of two functions that are both O(n):
- f1(n) = 1000000000n + 5
- f2(n) = 3n
It may seem that f1 does more work as n grows so it's not "fair" to say both are O(n). But their time complexity is bounded by a linear function: for some (large) constant c I can say that the runtime of both functions will be below f(n) = cn and thus the time complexity as a whole is O(n).