In Python, convert a list of integers into a binary tree

I have a list of integers that I want to convert into a binary tree, in Python. Each element should go to the next available position in the tree, going from left to right.

For example, the list of integers could be

root = [3,9,20,None,None,15,7]

If a node is None, then I want that node to be ignored when considering where to put a list element. So for the list

root = [2,None,3,None,4,None,5,None,6]

each element goes on its own level.

I can solve the problem when the list is exhaustive, ie each position in the tree is specified, even if it’s parent(s) are None; see below.

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def array_to_binary_tree(array):
    n = len(array)
    node = Node(array[0])
    nodes = []
    nodes.append(node)
    for i in range(0, n):
        left_index = i * 2 + 1
        if left_index < n:
            node_left = Node(array[left_index])
            nodes.append(node_left)
            nodes[i].left = node_left
        right_index = i * 2 + 2
        if right_index < n:
            node_right = Node(array[right_index])
            nodes.append(node_right)
            nodes[i].right = node_right
    root = nodes[0]
    return root

But I can’t solve it for when the array is giving a minimalist representation.

>Solution :

Your code seems to assume the input tree is a complete binary tree, as you use the i * 2 + 1 formula. But the tree represented in the example is not a complete one, and so that formula is not going to work.

Here is a function you could use:

from collections import deque

def array_to_binary_tree(lst):
    if not lst:
        return
    values = iter(lst)
    root = Node(next(values))
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node:
            children = [
                None if value is None else Node(value)
                for value in (next(values, None), next(values, None))
            ]
            queue.extend(children)
            node.left, node.right = children

    return root