Bug in build and levelorder function

[fuyb1992]

Tree:

    5 
  /    \
2       3
       /   \
      2     4
     / \
    3   1

Code:

from binarytree import build
li = [5, 2, 3, None, None, 2, 4, 3, 1]
build(li)

Error:

File "C:\Program Files\Python37\lib\site-packages\binarytree\__init__.py", line 1811, in build
    'parent node missing at index {}'.format(parent_index))

FYI:

def build(values):
    ...
    nodes = [None if x is None else Node(x) for x in data]
    non_null_nodes = [x for x in nodes if x is not None]
    for i in range(1, len(nodes)):
        if nodes[i] is not None:
            parent_index = (i - 1) // 2
            parent = non_null_nodes[parent_index]
    ...

def levelorder(self):
    ...
    current_level = [self]
    res = []
    while current_level:
        next_level = []
        for node in current_level:
            if node:
                res.append(node.val)
                next_level.append(node.left)
                next_level.append(node.right)
            else:
                res.append(None)
        current_level = next_level
    while res:
        if res[-1] is None:
            res.pop()
        else:
            break
    return res

[joowani]

Hi @fuyb1992,

It should be [5,2,3,None,None,2,4,None,None,None,None,3,1].

[fuyb1992]

Hi @joowani
[5,2,3,None,None,2,4,None,None,None,None,3,1] works, but it is confused that None node has child node.

[joowani]

Hi @fuyb1992,

it may seem unintuitive at first, but that's just how binary trees are represented in arrays. If there is a more succinct way, please let me know and I will consider adding it to the library. Thanks.