Error in Level Order Traversal of Binary Tree

November 25, 2022

What mistake have i done here ?

def levelOrder(root):
#Write your code here
que = []
que.append(root)
while que != []:
    coot = que.pop()
    print(coot.data,end=" ")

    if coot.left is not None:
        que.append(coot.left)

    if coot.right is not None:
        que.append(coot.right)

OutPut Expected:1 2 5 3 6 4

MY_output: 1 2 5 6 3 4

>Solution :

You are appending nodes to end end of the list que(using append()). And also removing the nodes from the end of the list que(using list.pop()), this would not preserve the order, so for something like

             1
            /  \
           2    3 
          / \   / \
         4   5  6  7

After first iteration would have que=[2, 3], and then you would pop 3 first instead of 2, which is incorrect. Instead, you should be popping 2, popping from the left(since you are appending the new nodes to the right).

So replacing coot = que.pop() with coot = que.pop(0) in your existing code should fix the issue. But note that list.pop(0) is a O(n) operation python. So I would suggest using collections.deque instead.

With deque, your code can be –

from collections import deque
def levelOrder(root):
    #Write your code here
    que = deque()
    que.append(root)
    while que != []:
        coot = que.popleft()
        print(coot.data,end=" ")

        if coot.left is not None:
            que.append(coot.left)

        if coot.right is not None:
            que.append(coot.right)