#| Для этого упражнения нет проверок.
Любое решение будет считаться успешным ответом. |#
а. Описание работы partial-tree
Процедура partial-tree строит сбалансированное бинарное дерево из первых n элементов списка elts, причем:

Сначала она рекурсивно строит левое поддерево из left-size = (n - 1) / 2 элементов.

Затем берет следующий элемент (сразу после левого поддерева) в качестве корня.

Оставшиеся right-size = n - left-size - 1 элементов используются для построения правого поддерева.

Результатом является пара: cons из:

построенного дерева

оставшегося списка (элементы, не попавшие в дерево)

Пример: (list->tree '(1 3 5 7 9 11))
Список имеет 6 элементов ⇒ n = 6

partial-tree будет работать следующим образом:

left-size = (6 - 1) / 2 = 2
→ Построим левое поддерево из (1 3)

Для (1 3):

left-size = (2 - 1) / 2 = 0

→ левое поддерево — пустое

Корень: 1

→ правое поддерево из одного элемента 3

левое и правое поддерево — пустые

→ дерево:

1
 \
  3
Корень основного дерева: следующий элемент — 5

right-size = 6 - 2 - 1 = 3
→ Построим правое поддерево из (7 9 11)

left-size = 1, значит:

левое поддерево: 7

корень: 9

правое поддерево: 11

→ дерево:

  9
 / \
7  11
Итоговое дерево:

       5
     /   \
    1     9
     \   / \
      3 7  11
б. Порядок роста числа шагов
Анализ:
На каждом уровне partial-tree делит список пополам (или почти пополам), строя левое и правое поддеревья рекурсивно. При этом:

Каждый элемент списка посещается ровно один раз, чтобы стать либо:

корнем узла

частью левого/правого поддерева

Количество шагов — пропорционально количеству узлов, т.е. O(n)

Ответ:
Порядок роста — Θ(n), где n — длина входного списка.