Разыскивается :Рекуррентная формула In -Метод вывода двоичного дерева порядка

Я немного застрял в поисках формулы повторения этого метода Java

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

Некоторые критерии:

• это полное бинарное дерево (у каждого внутреннего узла есть 2 дочерних узла, каждый лист имеет одинаковую глубину)
• дерево имеет n узлов и сложность O (n)

Я должен найти рекуррентную формулу по отношению к depth hдерева с n knots, и в качестве дополнительного бонуса мне нужно экстраполировать явную формулу, ведущую к O (n )из этого.

Вот что у меня получилось:

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

Я использовал пример d = 3, чтобы прояснить ситуацию для себя, у меня возникли трудности с его дальнейшим разбиением. Мое предположение вообще верно?

Изменить :Следующая попытка

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

Поскольку каждый уровень глубины дерева содержит ровно 2 ^ (h -1 )узлов, коэффициент h в строке 4 можно игнорировать, поскольку n более важен для конечного результата.