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

Question

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. (This array representation of binary trees come from Leetcode eg (https://leetcode.com/problems/minimum-depth-of-binary-tree/).)

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.

Answer 1

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:
            # Get next two values from input list, and 
            #   if they are not None, create a node for them
            children = [
                None if value is None else Node(value)
                for value in (next(values, None), next(values, None))
            ]
            # Append these two to the queue, and also attach them in the tree
            queue.extend(children)
            node.left, node.right = children

    return root

Here is an alternative that doesn't call iter explicitly, but uses for to iterate the values from the input list:

def array_to_binary_tree(lst):
    if not lst:
        return
    node = root = Node(lst[0])
    queue = deque()
    for i, value in enumerate(lst[1:]):
        if value is not None:  # A node to create?
            queue.append(Node(value))
            if i % 2:  # At odd iterations we attach it as a right child
                node.right = queue[-1]
            else:  # At even iterations we attach it as a left child
                node.left = queue[-1]
        if i % 2 and queue:  # After odd iterations we grab a next parent
            node = queue.popleft()

    return root