title: Worst case of traversing non-binary tree
body: <p>I've written a recursive algorithm that traverses a non-binary tree structure. The structure is consists of directories or files. </p>
  
  <p>The algorithm takes an input directory (<code>curDirectory</code>) and traverses the tree depth first. When it reaches the bottom of a branch, it looks for files and prints some info. It then returns one level, looks for files and prints stuff, and so on. We don't know the number of subdirectories or files in a directory. </p>
  
  <p>How do I analyze the worst and average case time for this algorithm? </p>
  
  <pre><code>for(int i = 0; i &lt; curDirectory.getChildren().size(); i++){
          if (curDirectory.getChildren().get(i) instanceof INodeDirectory)
              blockCounter = blockCounter + digAndCount((INodeDirectory)curDirectory.getChildren().get(i));
      }
  
      for(int i = 0; i &lt; curDirectory.getChildren().size(); i++){
          if (curDirectory.getChildren().get(i) instanceof INodeFile) {
              // print stuff and do other stuff 
          }
      }
  </code></pre>