{"id":1707,"date":"2020-06-11T11:41:10","date_gmt":"2020-06-11T11:41:10","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1707"},"modified":"2022-03-29T00:18:13","modified_gmt":"2022-03-29T00:18:13","slug":"levelorder-traversal","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/levelorder-traversal\/","title":{"rendered":"LevelOrder Traversal"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

BFS , Queue<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a binary tree, our task is to print the level order traversal of the tree.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

In level order traversal , each node is visited level-wise (level by level), starting from left to right. Simple solution is to print all the nodes at level 1, then level 2…..upto level h<\/code>, where h<\/code> is the height of the tree.<\/p>\n<\/blockquote>\n

Approach :<\/h4>\n
\n

We will use Queue to store the traversal, we need to traverse left to right (left node then right node), for each level.<\/p>\n

We will create an empty queue Q<\/code>, push the root node into Q<\/code>, & perform the following steps while Q<\/code> is not empty :<\/p>\n<\/blockquote>\n

    \n
  1. \n

    Extract the front node from Q<\/code> and store it in a temporary node pointer, i.e. temp = Q.front()<\/code>, print its value, & remove the front node ( Q.pop()<\/code>).<\/p>\n<\/li>\n

  2. \n

    If temp->left != NULL<\/code>, then push the left node in Q<\/code>. Do the same for right node.<\/p>\n<\/li>\n<\/ol>\n

    \n

    Below is the implementation of this aproach.<\/p>\n<\/blockquote>\n

    \"\"<\/p>\n

    Complexity Analysis :<\/h3>\n
    \n

    We are traversing every node once so time complexity of this approach is O(n)<\/code>.<\/p>\n<\/blockquote>\n

    SOLUTIONS:<\/h3>\n

    \t\t\t\t\t\t