Level Order Traversal in python, Can we optimise it better?

Question

def levelorder(root):
    if root is None:
        return
    mylist = [] #similar to use of queue
    mylist.append(root)
    while len(mylist) > 0:
        print(mylist[0])
        node = mylist.pop(0) #deque
        if node.left is not None:
            mylist.append(node.left)
        if node.right is not None:
            mylist.append(node.right)

This is the code i've written in python (something similar to use of queue date structure) for level order traversal but the problem here if we use mylist.pop(0), it will have time complexity of O(w) where, w is the width of the tree and in worst case if we have n nodes, it can go O(n^2). In C++, both enque and deque operation is O(1), hence we can do level order traversal in O(n) time.Can we do it O(n) in python?

EDIT: DONE

How to implemet it here, I tried using it but was unable to. Can you please post some relevant resources here? — Mayank Parashar, Oct 09 '21 at 19:24
Could you add some **tiny** sample data to test the implementation — Dani Mesejo, Oct 09 '21 at 19:25

Dani Mesejo · Answer 1 · 2021-10-09T19:32:15.030

Can we do it O(n) in python?

Yes, use collections.deque:

from collections import deque


def level_order(root):
    if root is None:
        return
    my_list = deque([])
    my_list.append(root)

    while my_list:
        print(my_list[0])
        node = my_list.popleft()
        if node.left is not None:
            my_list.append(node.left)
        if node.right is not None:
            my_list.append(node.right)

The computational complexity of deque.popleft is O(1) (see 1 and 2).

Overall Complexity

As the code passes by each node one time and all the operations are O(1) then the overall complexity of the traversal is O(n) where is n is the cardinality of the set of nodes.

score 0 · Answer 2 · answered Oct 09 '21 at 19:32

A rather simplified linear generator function:

def levelorder(root):
    if root:
        row = [root]
        while row:
            yield from row
            row = [c for n in row for c in (n.left, n.right) if c]

This can be easily turned into a list:

x = [*levelorder(some_root)]

Or implemented to return a list:

def levelorder(root): 
    result = []
    if root:
        row = [root]
        while row:
            result.extend(row)
            row = [c for n in row for c in (n.left, n.right) if c]
    return result

Level Order Traversal in python, Can we optimise it better?

2 Answers2