2
$\begingroup$

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?
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sid Dec 24 '14 at 16:47
  • $\begingroup$ You can try it out and see whether this optimization is worthwhile. It's hard to say in advance. $\endgroup$ – Yuval Filmus Dec 24 '14 at 19:31
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.