Convert binary tree to a list with level order in Python

Question

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!

Have you already attempted to create the list without the 'None's? i.e. do you have the code working for lever order without accounting for missing nodes? If not, try that first and post your attempt. — Aziz Sonawalla
– Aziz Sonawalla, Commented Dec 7, 2020 at 1:41
Why doesn't the list have None values for the children of the 2.5 node? Is the 2.5 node somehow different than the 0.52 which does contribute None to the final list? — Mark
– Mark, Commented Dec 7, 2020 at 2:03
I'm thinking that it only outputs until the height of the tree. since 2.5 is at the bottom of the tree, it does not have any 'None's attached to it. Whereas 0.52 is in the middle of the tree so we should consider both of its children are missing — FR.B
– FR.B, Commented Dec 7, 2020 at 2:07

Mark · Accepted Answer · 2020-12-07 04:05:47Z

2

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]

edited Dec 7, 2020 at 4:05

answered Dec 7, 2020 at 2:10

Mark

92.6k8 gold badges116 silver badges156 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mark Over a year ago

Thanks @BowlOfRed. You are of course correct. Attributing my error to weekend brain syndrome. Edited.

Collectives™ on Stack Overflow

Convert binary tree to a list with level order in Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related