Build a binary tree from a Python list

assuming your list is already in the order described by https://docs.python.org/3/library/heapq.html?highlight=heapq#theory you could do this (if it is not, use heapq.heapify):

def from_list(elements):
    root_node = TreeNode(x=elements[0])
    nodes = [root_node]
    for i, x in enumerate(elements[1:]):
        if x is None:
            continue
        parent_node = nodes[i // 2]
        is_left = (i % 2 == 0)
        node = TreeNode(x=x)
        if is_left:
            parent_node.left = node
        else:
            parent_node.right = node
        nodes.append(node)

    return root_node

i store all the nodes in a list called nodes. iterating over the elements i then know how to find the parent node in the nodes list.

using the recursive print function

def print_recursive(tree, level=0, prefix="root"):
    print(f"{level * '  '}{prefix:5s}: val={tree.val}")
    if tree.left:
        print_recursive(tree.left, level + 1, "left")
    if tree.right:
        print_recursive(tree.right, level + 1, "right")

and running it for your second example

tree = from_list(elements=[4, 6, 2, None, 5, 1, 9, 2, 1, 3, 4, None, 7])
print_recursive(tree)

i get:

root : val=4
  left : val=6
    right: val=5
      left : val=2
      right: val=1
  right: val=2
    left : val=1
      left : val=3
      right: val=4
    right: val=9
      right: val=7

I use the following function when solving LeetCode problems. It has these characteristics:

• It really uses LeetCode's input format, so it does not follow the heap-organisation, but skips entries when the corresponding parent is already None -- contrary to what the heap-format would do.
• It uses a queue so to insert nodes in the correct (breadth-first) order
• It uses an iterator over the input list

Code:

def to_binary_tree(items):
    if not items:
        return None

    it = iter(items)
    root = TreeNode(next(it))
    q = [root]
    for node in q:
        val = next(it, None)
        if val is not None:
            node.left = TreeNode(val)
            q.append(node.left)
        val = next(it, None)
        if val is not None:
            node.right = TreeNode(val)
            q.append(node.right)
    return root

You can refactor the code like this. It will take a list of numbers or string and will build a BST but for simple binary tree, only one if condition will needs to be removed.

def add_child(self, val):
    if val == self.val:
        return
    
    elif val < self.val:
        if self.left:
            self.left.add_child(val)
        else:
            self.left = BinarySearchTree(val)
    else:
        if self.right:
            self.right.add_child(val)
        else:
            self.right = BinarySearchTree(val)

def build_tree(elements):
     root = BinarySearchTree(elements[0])
     for i in range(1, len(elements)):
         root.add_child(elements[i])

     return root

if __name__=="__main__":
     numbers = [15, 10, 8, 12, 20, 16, 25]        
     root = build_tree(numbers)

You could iterate over your elements and convert the list to a tree this way. This isn't very memory efficient (it will store a pointer to each node on the queue so you're looking at O(N) in terms of data) but it will be more efficient in terms of CPU, especially in Python.

def build_tree(data):

    # Check if we have data; if we don't then return None
    if not data:
        return None

    # Create our tree object from the root and then
    # add it to a list of nodes that we can add data to
    tree = TreeNode(data[0])
    queue = [data[0]]    

    # Iterate over the rest of the nodes and add
    # them to the tree
    index = 0
    for i in range(1, len(data) - 1):

        # If our node is None then we have a leaf so
        # there's no work to do; otherwise, create the
        # node and add it to the proper spot
        if data[i] != None:

            # Create the node from the data
            node = TreeNode(data[i])

            # If the index we're looking at is even
            # then we have a left branch; otherwise we
            # have a right branch so add the node to the
            # appropriate side of the tree
            if i % 2 == 0:
                queue[index].left = node
            else:
                queue[index].right = node)

            # Add the node to our queue so it can
            # be referenced later
            queue.append(node)

        # Finally, update our index if we've finished looking
        # at this node. As each branch may only have two children
        # we only need to do this if we're looking at odd-indexed
        # entries because leaves will always be None (unless we've
        # reached the last level of the tree)
        index += i % 2

    return tree

This algorithm works by building a queue from the data (which already had a heap structure anyway) while creating the nodes. Because the queue is iterated only when the current node is full and because it iterates left-to-right, the order of the tree will be preserved.