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

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?

CodePudding user response：

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.

CodePudding user response：

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