Wanted: In-Order Binary Tree Output Method Repeat Formula

Question

I slowed down the search for a recurrence formula for 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 complete binary tree (each internal node has 2 children, each leaf has the same depth)
• the tree has n nodes and complexity O (n)

I need to find a repetition formula with respect to depth h tree with n knots , and as an added bonus I need to extrapolate an explicit formula leading to O (n) from this.

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 the situation for myself, I have difficulties with this. Is my assumption even correct?

---

Edit: Next things try

 [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) 

Since each tree depth level contains exactly 2 ^ (h-1) nodes, the factor h in line 4 can be ignored, since n is more suitable for the final result.

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 =
^ 0 2 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ LGN =
(2 ^ (lgn + 1) -1) / (2-1) = 2 * 2 ^ lgn =
2n.

Answer 2

Here, an alternative approach is used using the Smoothness rule (Levitin, The Design and Analysis of Algorithms, 2nd ed., 481-82), which allows, instead, the recurrence relation to be represented as an indicator.

Any approach is suitable for this problem - forward or reverse replacement. In many cases, I find reverse substitution easier to digest.