How to convert a pyramid into a binary tree

Question

Let's say I have a pyramid like this, but larger

and want to convert it into a binary tree, meaning we actually want to have a tree like this:

            2
       4         9
    4    9     9    6
   7 7  7  8  7  8  8 9

In a list format the result would be

2,4,9,4,9,9,6,7,7,7,8,7,8,8,9

I tried the following way, but it only works for trees of length 4. As an input I take a tree in a txt file.

def give_input(name):
    index = 0
    lis_of_listas = []
    f = open(name, "r")
    for x in f:
        x = x.replace(' ', '')
        x = x.replace('
', '')
        lista = [int(i) for i in list(x)]
        if (index > 1 and index % 2 == 0):
            podlista = lista[1:-1]
            podpodlista = []
            for i in podlista:
                podpodlista.append(i)
                podpodlista.append(i)
            podpodlista.append(lista[-1])
            podpodlista.insert(0, lista[0])
        elif (index > 1 and index % 2 == 1):
            podlista = lista[1:-1]
            print(len(podlista)/2)
            podlista1 = podlista[0:int(len(podlista) / 2)]
            podlista2 = podlista[int(len(podlista) / 2):len(podlista)]
            podpodlista = []
            for i in podlista1:
                podpodlista.append(i)
                podpodlista.append(i)
            podpodlista.append(podlista1[-1])
            podpodlista.append(podlista2[0])
            for j in podlista2:
                podpodlista.append(j)
                podpodlista.append(j)
            podpodlista.append(lista[-1])
            podpodlista.insert(0, lista[0])
        if index <= 1:
            lis_of_listas.append(lista)
        else:
            lis_of_listas.append(podpodlista)
        index += 1
    return [item for sublist in lis_of_listas for item in sublist]

user_6792743 · Answer

We can see that for each element with index j in the parent row, we need to take elements with indices j and j+1 in the next row:

For example, to go from row 2 with indices ix = [0, 1] to row 3 in a binary tree, we would take indices in row 2 and split each of them into its children j => [j, j+1], making it ix = [0, 1, 1, 2] in row 3.

Similarly, row 4 can be calculated from row 3 by splitting ix = [0, 1, 1, 2] with the same logic into [0, 1, 1, 2, 1, 2, 2, 3], and so on.

Based on these index arrays we can create a binary tree:

Now what's left to get the actual list representation of a binary tree is just concatenating the index lists and taking the values at these indices.

Here's how this can be done in code:

s = \
"""  2
    4 9
   4 9 6
  7 7 8 9"""

# convert string to a list of lists (row, values)
# l = [['2'], ['4', '9'], ['4', '9', '6'], ['7', '7', '8', '9']]
l = [x.split() for x in s.split('
')]


# init
out = [l[0][0]]   # store output here, init with root
ix = [0]          # indices of the previous row

# loop
for i in range(len(l)-1):
    ix_new = []              # indices for the new row
                             # if parent has index (j), then
                             # - left child will have index (j)
                             # - right child will have index (j+1)
    for j in ix:
        ix_new.append(j)     # left
        ix_new.append(j+1)   # right
    ix = ix_new
    
    # appending elements with corresponding indices to out:
    for k in ix_new:
        out.append(l[i+1][k])

out

Output:

['2', '4', '9', '4', '9', '9', '6', '7', '7', '7', '8', '7', '8', '8', '9']

P.S. For those interested in getting a visual representation of the tree from the list format, please see this question

user_3840170 · Answer

Here’s a simple way that mutates:

from dataclasses import dataclass

@dataclass
class Node:
    value: int
    left: object
    rite: object

def tree_from_list(l, depth):
    l = iter(l)
    root = Node(next(l), None, None)
    leaves = [root]
    for _ in range(depth):
        new_leaves = [Node(next(l), None, None)]
        for leaf in leaves:
            leaf.left = new_leaves[-1]
            leaf.rite = Node(next(l), None, None)
            new_leaves.append(leaf.rite)
        leaves = new_leaves
    return root

The above uses the same object for the left and the right branch of the tree, thus conserving memory.

Usage:

def print_tree(node, indent=''):
    if node is None:
        return
    print(indent + str(node.value))
    print_tree(node.left, indent=indent+'  ')
    print_tree(node.rite, indent=indent+'  ')

print_tree(tree_from_list([
          1,
        2,  3,
      4,  5,  6,
], depth=2))

This should print:

user_5587393 · Answer

The solution is far easier than you could imagine. First, think of your pyramid as a graph where the node on level l and index i is linked with the two nodes

level l + 1, index i
level l + 1, index i + 1

Now you explore your graph starting from the only node on level 0 in a pre-order way and you will notice that the same node can be found on many paths, that corresponds to the duplicated entries in the binary tree. for example, to find node 8, there are these paths:

I just realize that it is probably easier if I show you the code:

pyramid = [(2,), (4,9), (4,9,6), (6,7,8,9), (1,2,3,4,5)]
final_tree = [[] for _ in range(len(pyramid))]

def pyramid_visit(pyramid, cur_lvl, cur_index):
    if cur_lvl == len(pyramid):
        return
    
    final_tree[cur_lvl].append(pyramid[cur_lvl][cur_index])
    pyramid_visit(pyramid, cur_lvl + 1, cur_index)
    pyramid_visit(pyramid, cur_lvl + 1, cur_index + 1)

pyramid_visit(pyramid, 0, 0)
print(final_tree)

And returns:

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

Try with a pyramid 3 levels high, very similar to a tree:

Next add a level, and identify the 2 underlying pyramids:

      1                 1
     /                   \
    2   3             2   3
   / \                   / \
  4   9   4         4   9   4
 / \ / \               / \ / \
4   9   6   5     4   9   6   5

You should clearly see the 2 subtrees, this is the recursive reasoning behind my solution.

How to convert a pyramid into a binary tree

3 Answers