More efficient DFS on trees

Lets say for simplicity sakes I have a simple balanced binary tree of height h and I am doing Depth First Search. I generally do the following skeletons:

def dfs(node root):
    //Pre actions
    if not node:
        return

    dfs(node.left)
    dfs(node.right)

    // Post actions

Now when I look at this code I know its worst case asymptotic bound is O(n). But perhaps I can do better in some cases. So I want to ask a few things and see if you guys agree:

• If the last level of the tree is very sparse. We will still make all those recursive calls when node->left and node-> right is null. these will be $2^h$ checks. Would I be correct in arguing that we should place an additional check in the pre conditions check to avoid at least some of those $2^h$ extra calls?

`

if not node.left and not node.right:
    return

or go even further and add an additional check:

if not node.right.left and not node.right.left:
     // Do some book keeping 
     return
 if not node.left.left and not node.left.right:
     // Do some book keeping 
     return

IOW is it legit to argue that in cases where the last level is mostly empty, calling dfs recursively is less(much less in certain languages?) performant vs doing the above additional checks at that last level and though we will still be worst case O(n) time bound(we visit everything), we can be better in such cases?

• Do compiler optimizations render my point (1) moot in certain cases. What are those cases?

If you want to cover the entire tree then your algorithm must run in $\Omega(n)$, assuming $n$ is the number of nodes in the tree. You are right, however, that you could optimize the code by checking that the child is non-empty before calling the function. This is an optimization that the compiler probably wouldn't do on its own. This optimization could improve your algorithm, but its running time will still be asymptotically $O(n)$ (assuming $O(1)$ processing per node); at most you improve the constant.

StackExchange Computer Science Q#35624, answer score: 4