How to create binary tree from level order traversal?

user_6065030 0
Viewed 683

Given a level_order list, which can include None values, how can a binary tree be constructed adhering to None values in the list i.e None nodes can't have any children (left or right values).

from typing import List, Optional

class Node():
    def __init__(val: int=None, left: Optional[Node]=None, right: Optional[Node]=None):
        self.val = val
        self.left = left
        self.right = right

def binary_tree(level_order: List, root=None): -> Node:
    pass

For example, when level_order is [4, -7, -3, None, None, -9, -3, 9, -7, -4, None, 6, None, -6, -6, None, None, 0, 6, 5, None, 9, None, None, -1, -4, None, None, None, -2], the tree should look like this enter image description here

And when the level_order is [1, 2, 3, 4, 5], the tree should look like enter image description here

The following code generates binary tree while not respecting the None values in the list

def binary_tree(level_order, root=None):
    ls = []

    def insert_value(data, root):
        newnode = Node(data)
        if len(ls) != 0:
            temp = ls[0]

        if root is None:
            root = newnode

        elif temp.left is None:
            temp.left = newnode

        elif temp.right is None:
            temp.right = newnode
            _ = ls.pop(0)

        ls.append(newnode)
        return root

    for i in range(len(level_order)):
        root = insert_value(level_order[i], root)

    return root

But the above code results in the following incorrect tree enter image description here

binary-tree python
1 Answers

How do you get a level-order list of nodes from a tree in the first place? Well, you return every element from a breadth-first traversal of the tree. To rebuild the tree from a level-order list, then, we can traverse the tree in a breadth-first way.

When we insert each element, starting with the root, add it to a queue. Then, once we finish adding both the left and right children of a node, pull the next node from the queue. Once we run out of elements to add, just return the root.

from typing import List, Optional

class Node():
    def __init__(self, val: int=None, left: Optional['Node']=None, right: Optional['Node']=None):
        self.val = val
        self.left = left
        self.right = right

def binary_tree(level_order: List) -> Node:
    values = iter(level_order)
    root = Node(next(values))
    nodes_to_fill = [root]
    try:
        while True:
            next_node = nodes_to_fill.pop(0)
            new_left = next(values)
            if new_left is not None:
                next_node.left = Node(new_left)
                nodes_to_fill.append(next_node.left)
            new_right = next(values)
            if new_right is not None:
                next_node.right = Node(new_right)
                nodes_to_fill.append(next_node.right)
    except StopIteration:
        return root

This is the same mechanism as breadth-first search would use, except in this case we're using it to construct the tree, rather than to search it.

For slightly more efficiency, if your tree is very large, you could probably use a queue.Queue instead of a list.

user_26488110
Related