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

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.

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

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, *, *>, *>>>

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

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)

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

If the input can specify None to indicate that there is no node in that position, and this means that no subsequent entries in the input will cover that virtual subtree, then you cannot use the formula 2*i+1.

Here is code to deal with such input format:

class TreeNode:
    def __init__(self, val: int) -> None:
        self.val = val
        self.left = self.right = None
        
    def __repr__(self):
        s = ""
        if self.right:
            s += "  " + repr(self.right).replace("\n", "\n  ") + "\n"
        s += repr(self.val)
        if self.left:
            s += "\n  " + repr(self.left).replace("\n", "\n  ")
        return s

def to_binary_tree(items: list[int]) -> TreeNode:
    if not items or items[0] is None:
        return
    values = iter(items)
    nodes = [TreeNode(next(values))]
    for node in nodes:
        for attr in ("left", "right"):
            value = next(values, None)
            if value is not None:
                child = TreeNode(value)
                setattr(node, attr, child)
                nodes.append(child)

    return nodes[0]
    

tree = to_binary_tree([5, 2, 3, 9, None, 6, 8, 11, 12, 14])
print(tree)

Your list is has the same internal structure as a binary heap. Except that it is not sorted like one. The package abstracttree (made by me) can provide a treeview of this structure.

It can be used like this:

from abstracttree import HeapTree, print_tree

# Not a (true) heap yet, but maybe use heapq.heapify
heap = [3,5,2,1,4,6,7,8,9,10,11,12,13,14]
tree = HeapTree(heap)

# To print use
print_tree(htree, "{.value}")

3
├─ 5
│  ├─ 1
│  │  ├─ 8
│  │  └─ 9
│  └─ 4
│     ├─ 10
│     └─ 11
└─ 2
   ├─ 6
   │  ├─ 12
   │  └─ 13
   └─ 7
      └─ 14

It only provides a tree view, so the original heap can still be edited using functions in heapq and changes will be reflected accordingly. Your list is not a heap yet, but heapq.heapify would fix that.

You can do this with bigtree Python package which supports binarytree and also regular trees and DAGs as well. Trees are easily created from list/dictionary/dataframe.

For your case, it can be done as such

>>> from bigtree import list_to_binarytree
>>> root = list_to_binarytree([3,5,2,1,4,6,7,8,9,10,11,12,13,14])
>>> root.vshow()
                          ┌───┐                            
                          │ 3 │                            
                          └─┬─┘                            
            ┌───────────────┴───────────────┐              
          ┌─┴─┐                           ┌─┴─┐            
          │ 5 │                           │ 2 │            
          └─┬─┘                           └─┬─┘            
     ┌──────┴───────┐               ┌───────┴───────┐      
   ┌─┴─┐          ┌─┴─┐           ┌─┴─┐           ┌─┴─┐    
   │ 1 │          │ 4 │           │ 6 │           │ 7 │    
   └─┬─┘          └─┬─┘           └─┬─┘           └─┬─┘    
  ┌──┴───┐      ┌───┴───┐       ┌───┴───┐       ┌───┴───┐  
┌─┴─┐  ┌─┴─┐  ┌─┴──┐  ┌─┴──┐  ┌─┴──┐  ┌─┴──┐  ┌─┴──┐  ┌─┴─┐
│ 8 │  │ 9 │  │ 10 │  │ 11 │  │ 12 │  │ 13 │  │ 14 │  │   │
└───┘  └───┘  └────┘  └────┘  └────┘  └────┘  └────┘  └───┘

Source: I'm the author of bigtree ;)