title: Wanted: Recurrence Formula of In-Order binary tree output method
body: <p>I'm in a bit of a jam searching for the recurrence formula of this java method</p>
  
  <pre><code>void printInorder(Node&lt;T&gt; v) {
      if(v != null) {
          printInorder(v.getLeft());
          System.out.println(v.getData());
          printInorder(v.getRight());
      }
  }
  </code></pre>
  
  <p>Some criteria:</p>
  
  <ul>
  <li>its a complete binary tree (every inner knot has 2 children, every leaf has the same depth)</li>
  <li>the tree has n knots and a complexity of O(n)</li>
  </ul>
  
  <p>I have to find the the recurrence formula in relation to the <code>depth h</code> of the tree with <code>n knots</code>, and as an added bonus, i need to extrapolate the explicit formula leading to O(n) from that.</p>
  
  <p>Now, this is what I got:</p>
  
  <pre><code>d = depth of the tree
  c = constant runtime for execution of the method itself
  d = 1: T(n) = c
  d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c
  </code></pre>
  
  <p>I used the example d = 3 to clarify things for myself, I'm having difficulties breaking this down further. Is my assumption even correct?</p>
  
  <hr>
  
  <p>Edit:
  Next attempt at things </p>
  
  <pre><code>[x] = { x in real numbers : max([x]) &lt;= x }, [x] rounded down to next full number
  d = 1: T(d) = 1
  d &gt; 1: T(d) = 2^(h-1) * T(n/(2^(h-1)))
  
  1: T(h)  = T(i = 0) + T(i = 1) + ... T(i = h-1)
  2: T(h) &lt;= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2)))
  3: T(h)  = n + n + ... + n
  4: T(h)  = (h-1)n
  5: T(h)  = O(n)
  </code></pre>
  
  <p>Because every level of depth of the tree contains exactly 2^(h-1) nodes, the h factor in line 4 can be ignored because n is more relevant for the final outcome.</p>