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

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 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])