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?