CODEWITHSUNDEEP
pythonlistbinary-treebreadth-first-search
H.Bian
H.Bian

Reputation: 19

Convert binary tree to a list with level order in Python

I have not found any related questions yet.

So the problem is: given an incomplete binary tree, say the root of the tree, how can I convert it into a list in level order in Python such that the empty nodes (missing nodes in that level) are represented as "None" in the list.

For example, I have this tree:

     1
   /   \
 4      0.52
/ \      / \
   2.5

I want to get the following list:

[1, 4, 0.52, None, 2.5, None, None]

by using some function like:

list = toList(root)

In addition, I have tree structured like this:

class TreeNode:

def __init__(self, value, isLeaf):

    self.left = None
    self.right = None
    self.value = value
    self.isLeaf = isLeaf

And borrow the solution from another post (to a list without 'None' taken place):

def toList(root):
    node_list = []
    thislevel = [root]
    while thislevel:
        nextlevel = list()
        
        for n in thislevel:
            # print(n.value)
            node_list.append(n.value)

            if n.left: 
                nextlevel.append(n.left)
            if n.right: 
                nextlevel.append(n.right)
        # print
        thislevel = nextlevel
    return node_list

my_list = toList(root)
print(my_list)

This gives the following so far:

[1, 4, 0.52, 2.5]

I am stuck here, don't know how to properly insert 'None' into the list...

Thanks!

Upvotes: 1

Views: 1275

Answers (1)

Mark
Mark

Reputation: 92440

You typically make a breadth-first iteration of a graph by using a queue. This is a first-in, first-out data structure. You start by adding the root to the queue, and then while the queue has items in it, you pop out the oldest one, add it to the results and the push its children into the queue. If you are doing this for anything other than small input, python’s collections.deque is more efficient than the list used here:

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

        
def breadth_first(t):
    q = [t]
    while q:
        current = q.pop(0)
        yield current.value if current else None
        if current and not current.isLeaf:
            q.extend([current.left, current.right])
        
            
t = TreeNode(1, False)
t.left = TreeNode(4, False)
t.right = TreeNode(0.52, False)
t.left.right = TreeNode(0.2

list(breadth_first(t))
# [1, 4, 0.52, None, 0.25, None, None]

Upvotes: 2

Related Questions