Wanted: Recurrence Formula of In-Order binary tree output method

Question

I'm in a bit of a jam searching for the recurrence formula of this java method

void printInorder(Node<T> v) {
    if(v != null) {
        printInorder(v.getLeft());
        System.out.println(v.getData());
        printInorder(v.getRight());
    }
}

Some criteria:

• its a complete binary tree (every inner knot has 2 children, every leaf has the same depth)
• the tree has n knots and a complexity of O(n)

I have to find the the recurrence formula in relation to the depth h of the tree with n knots, and as an added bonus, i need to extrapolate the explicit formula leading to O(n) from that.

Now, this is what I got:

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

I used the example d = 3 to clarify things for myself, I'm having difficulties breaking this down further. Is my assumption even correct?

---

Edit: Next attempt at things

[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number
d = 1: T(d) = 1
d > 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) <= (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)

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.

Answer 1

T(n) = T(n/2) + T(n/2) + 1

• Level 0 has 1 operation.

• Level 1 has 2 operations.

• Level 2 has 4 operations.

• Level k has 2^k operations.

• The depth of the tree is lgn.

1+2+...+2^lgn=
2^0+2^1+2^2+...+2^lgn=
(2^(lgn + 1)-1)/(2-1)=2*2^lgn=
2n.