Best way to construct a binary tree from a list in python

Question

Assuming each node has self.left, self.right and self.data, whats the best way to construct a binary tree, not a binary search tree (BST), from a list where the numbers are given per level. Where the first number is level 1, next 2 are level 2, next 4 are level 3, and so on. For example

input: [3,5,2,1,4,6,7,8,9,10,11,12,13,14] 

constructs a tree:

          3
       /     \
     5         2
    /\         /\
   1  4       6   7
  /\  /\     /\   /\
 8 9 10 11 12 13 14

One solution is:

for node at index i,
left child index = 2i+1
right child index = 2i+2

Wondering if there are other possible ways

Answer 1

I went through some of the answers above, and modified some of it and created a solution that worked for a tree I was working on: [5,4,8,11,None,13,4,7,2,None,None,None,1]

The trick is, push "None" to the correct index whenever you encounter a "None" in your list. And to check the index going out of bound, keep checking it with updated list, instead of the previous n = len(items).

I think it will work for most of the cases.

Pasting my code here:

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

def to_binary_tree(items: list[int]) -> TreeNode: 
    if len(items) <= 0:
        return None

    def inner(index: int = 0) -> TreeNode:
        if len(items) <= index:
            return None

        elif items[index] is None:\
            # identify the index and add null to them in the list
            items.insert(2 * index + 1, None)
            items.insert(2 * index + 2, None)
            return None

        node = TreeNode(items[index])
        node.left = inner(2 * index + 1)
        node.right = inner(2 * index + 2)
        return node

    return inner()

Answer 2

class TreeNode:
    def __init__(self, val: int, left=None, right=None) -> None:
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self) -> str:
        return f"val: {self.val}, left: {self.left}, right: {self.right}"

    def __str__(self) -> str:
        return str(self.val)


def to_binary_tree(items: list[int]) -> TreeNode:
    """Create BT from list of values."""
    n = len(items)
    if n == 0:
        return None

    def inner(index: int = 0) -> TreeNode:
        """Closure function using recursion bo build tree"""
        if n <= index or items[index] is None:
            return None

        node = TreeNode(items[index])
        node.left = inner(2 * index + 1)
        node.right = inner(2 * index + 2)
        return node

    return inner()

Usage:

root = to_binary_tree([1, 2, 3, None, None, 4, 5])

Answer 3

Here is a quick solution I came up with:

class BT_Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def __str__(self):
        return f'<{self.data}, {self.left}, {self.right}>'


def build_binary_tree(values, index):
    if len(values) == 0:
        raise Exception('Node list is empty')

    if index > len(values) - 1:
        raise Exception('Index out of range')

    root = BT_Node(values[index])
    if 2*index+1 < len(values):
        root.left = build_binary_tree(values, 2*index+1)
    if 2*index+2 < len(values):
        root.right = build_binary_tree(values, 2*index+2)

    return root

Answer 4

You can directly use this tool: drawtree by pip install drawtree, and if you are curious about its implementation you can refer to this source code: https://github.com/msbanik/drawtree.

For your case in the question:

from drawtree import draw_level_order
draw_level_order('[3,5,2,1,4,6,7,8,9,10,11,12,13,14]')

And you will get the text graph like the following:

               3
              / \
             /   \
            /     \
           /       \
          /         \
         /           \
        /             \
       /               \
      5                 2
     / \               / \
    /   \             /   \
   /     \           /     \
  1       4         6       7
 / \     / \       / \     /
8   9   /   \     /   \   14
       10   11   12   13

In addition, you can try Graphviz.

Answer 5

One way to do it is to build a fringe of the current leaves.

Assuming a Node class:

class Node(object):
    def __init__(self, data):
        self.data = data
        self.left = '*'
        self.right = '*'
    def __str__(self):
        return f'<{self.data}, {self.left}, {self.right}>'  # Py 3.6

Then you can just manage the fringe and iterate over the data:

from collections import deque

data = [3,5,2,1,4,6,7,8,9,10,11,12,13,14]
n = iter(data)
tree = Node(next(n))
fringe = deque([tree])
while True:
    head = fringe.popleft()
    try:
        head.left = Node(next(n))
        fringe.append(head.left)
        head.right = Node(next(n))
        fringe.append(head.right)
    except StopIteration:
        break

print(tree)
# <3, <5, <1, <8, *, *>, <9, *, *>>, <4, <10, *, *>, <11, *, *>>>, <2, <6, <12, *, *>, <13, *, *>>, <7, <14, *, *>, *>>>

Answer 6

Here is one way to implement your solution: create a list of tree nodes, each with index position corresponding to the original data list. Then, we can fix up the left- and right links.

import logging

logging.basicConfig(level=logging.DEBUG)
logger = logging.getLogger(__name__)

class Tree(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def __repr__(self):
        left = None if self.left is None else self.left.data
        right = None if self.right is None else self.right.data
        return '(D:{}, L:{}, R:{})'.format(self.data, left, right)

def build_tree_breadth_first(sequence):
    # Create a list of trees
    forest = [Tree(x) for x in sequence]

    # Fix up the left- and right links
    count = len(forest)
    for index, tree in enumerate(forest):
        left_index = 2 * index + 1
        if left_index < count:
            tree.left = forest[left_index]

        right_index = 2 * index + 2
        if right_index < count:
            tree.right = forest[right_index]

    for index, tree in enumerate(forest):
        logger.debug('[{}]: {}'.format(index, tree))
    return forest[0]  # root

def main():
    data = [3, 5, 2, 1, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14]
    root = build_tree_breadth_first(data)
    print 'Root is:', root

if __name__ == '__main__':
    main()

Output:

DEBUG:__main__:[0]: (D:3, L:5, R:2)
DEBUG:__main__:[1]: (D:5, L:1, R:4)
DEBUG:__main__:[2]: (D:2, L:6, R:7)
DEBUG:__main__:[3]: (D:1, L:8, R:9)
DEBUG:__main__:[4]: (D:4, L:10, R:11)
DEBUG:__main__:[5]: (D:6, L:12, R:13)
DEBUG:__main__:[6]: (D:7, L:14, R:None)
DEBUG:__main__:[7]: (D:8, L:None, R:None)
DEBUG:__main__:[8]: (D:9, L:None, R:None)
DEBUG:__main__:[9]: (D:10, L:None, R:None)
DEBUG:__main__:[10]: (D:11, L:None, R:None)
DEBUG:__main__:[11]: (D:12, L:None, R:None)
DEBUG:__main__:[12]: (D:13, L:None, R:None)
DEBUG:__main__:[13]: (D:14, L:None, R:None)
Root is: (D:3, L:5, R:2)