# 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:

1. 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?

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

## 2 Answers

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.

• Yes but while I agree with the asymptotic upper bound. I am not sure its tight with this optimization(assuming ofcourse I have reason to believe my case is true). The fraction of nodes that vary between any 2 levels is: $\frac{1}{2}(1+\frac{1}{N})$ . Which is roughly 50% of the nodes asymptotically. – Sid Dec 24 '14 at 16:47
• You can try it out and see whether this optimization is worthwhile. It's hard to say in advance. – Yuval Filmus Dec 24 '14 at 19:31

While this indeed saves recursive calls, DFS is often described by recursion for convenience of writing/implementing.

Notice that you can actually unroll the entire recursion tree and implement iterative DFS.