Создание бинарного дерева снизу вверх

Question

Рассмотрим следующую программу, которая строит двоичное дерево сверху вниз, разбивая узлы пополам:

def split(n):
    if n == 1:
        return n
    m = n//2
    return [split(n-m)] + [split(m)]

Например:

for i in range(1, 10):
    print(i, split(i))

печатает:

1 1
2 [1, 1]
3 [[1, 1], 1]
4 [[1, 1], [1, 1]]
5 [[[1, 1], 1], [1, 1]]
6 [[[1, 1], 1], [[1, 1], 1]]
7 [[[1, 1], [1, 1]], [[1, 1], 1]]
8 [[[1, 1], [1, 1]], [[1, 1], [1, 1]]]
9 [[[[1, 1], 1], [1, 1]], [[1, 1], [1, 1]]]

Можно ли построить точно такое же дерево снизу вверх?То есть, учитывая число 1, рекурсивно объединяйте два смежных узла, пока больше нечего объединять?

Если нет, возможно ли построить похожее дерево снизу вверх с точно такой же высотой?

Чтобы проиллюстрировать процесс, возьмем, к примеру, 6:

1, 1, 1, 1, 1, 1
[1, 1], 1, 1, 1, 1
[1, 1], 1, [1, 1], 1
[[1, 1], 1], [1, 1], 1
[[1, 1], 1], [[1, 1], 1]
[[[1, 1], 1], [[1, 1], 1]]

Как узнать, когда нужно «пропустить» узел, чтобы он позже был объединен?

PS: Пример написан на Python, но язык не имеет значения.

Answer 1

Let n be the initial size of the array 
for(int i=0;i<log2(n);i++)
{
    Let the current size of the array be m
    for(int j=0;j<m/2;j++)
        merge two adjacent elements of the array to form a new element
    // After this some elements from first half would be single

    for(int j=m/2;j<m;j++)
        merge two adjacent elements of the array to form a new element.  
    // After this some elements from second half would be single

    // The new updated array will now have ceil(n/2) elements
}