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.

In root = [2,null,3,null,4,null,5,null,6] the null means None I presume!? — destructioneer
– destructioneer, Commented Jul 10, 2023 at 10:16
@destructioneer Yes null means None, thanks. It's fixed now. — Soulfire
– Soulfire, Commented Jul 10, 2023 at 10:19
How exactly is [2,None,3,None,4,None,5,None,6] a tree representation. Can you show the desired output? — user2390182
– user2390182, Commented Jul 10, 2023 at 10:34
This is clearly a LeetCode problem, because they use null in the textual representation of a tree/node, which you’ve copy-pasted. Is there a specific LeetCode problem you’re trying to solve? — Abhijit Sarkar
– Abhijit Sarkar, Commented Jul 10, 2023 at 10:54
This syntax of representing a binary tree by an array, and the array examples I showed, comes from Leetcode. I edited to include this in my question. — Soulfire
– Soulfire, Commented Jul 10, 2023 at 12:39

trincot · Accepted Answer · 2023-07-10 11:18:14Z

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

edited Jul 10, 2023 at 11:18

answered Jul 10, 2023 at 10:22

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user2390182 Over a year ago

My only beef with this is using a list as a queue =)

trincot Over a year ago

@user2390182, OK, used a deque instead.

Soulfire Over a year ago

Thanks! Could you please, if you feel like it, explain what this code does, and in particular why we need to use iter()?

trincot Over a year ago

There is no absolute need to use iter, it is just a nice feature of Python. You can also use an index variable i like you did, and increment it each time you take a value from the input list.

trincot Over a year ago

I added a few code comments and an alternative that does not use iter.

Alain T. · Accepted Answer · 2023-07-10 17:37:54Z

0

This form of tree in a list is a binary heap tree. Children of a given index i are at i*2+1 and i*2+2 for left and right respectively and parents are at (i-1)//2.

This should allow you to process them sequentially, replacing each value in the list by the corresponding node:

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

root[0] = Node(root[0])
for i,n in enumerate(root):
    if n is None: continue
    root[i] = Node(n)
    if i%2:
        root[(i-1)//2].left  = root[i]
    else:
        root[(i-1)//2].right = root[i]

answered Jul 10, 2023 at 17:37

Alain T.

42.2k4 gold badges36 silver badges57 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

5 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related