title: Why are there only log(N) recursive calls made in this tree traversal?
body: <p>The following code is the solution to this problem: "Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked list".</p>
  
  <pre><code>void createLevelLinkedList(TreeNode root, ArrayList&lt;LinkedList&lt;TreeNode&gt;&gt;lists, int level) {
  
     if(root == null) return; //base case
  
     LinkedList&lt;TreeNode&gt; list = null;
     if (lists.size()==level){ //Level not contained in list
        list = new LinkedList&lt;TreeNode&gt;();
        lists.add(list);
     } else{
       list = lists.get(level);
     }
  
     list.add(root);
     createLevelLinkedlist(root.left, lists, level+1);
     createLevelLinkedList(root.right, lists, level+1);
  }
  
  ArrayList&lt;LinkedList&lt;TreeNode&gt;&gt; createLevelLinkedList(TreeNode root){
  
     ArrayList&lt;LinkedList&lt;TreeNode&gt;&gt; lists = new ArrayList&lt;LinkedList&lt;TreeNode&gt;&gt;();
  
     createLevelLinkedlist(root, lists, 0);
     return lists;
  
  }
  
  </code></pre>
  
  <p>According to the solution, this code has a runtime of O(N) but uses O(log N) recursive calls. Why would there only be O(log N) recursive calls? It looks like within each call, there are always two new recursive calls made to <code>root.left</code> and <code>root.right</code>, so shouldn't there be O(N) recursive calls? One for each node in the tree?</p>
  
  <p>"The solution uses O(log N) recursive calls (in a balanced tree), each of which adds a new level to the stack"  </p>
  
  <p>Sorry, am really confused, would appreciate an explanation thanks!</p>