Question

The level-order listing of the nodes of a tree first lists the root, then all nodes of depth 1, then all nodes of depth 2, and so on. Nodes at the same depth are listed in left-to-right order. Write a program to list the nodes of a tree in level-order.

Answer 1

#include<bits/stdc++.h>

using namespace std;

class Node{

public:

int data;

Node * left;

Node * right;

Node(int data)

{

this->data=data;

this->left=NULL;

this->right=NULL;

}

};

void levelOrdertraversal(Node* root)

{

queue<Node*> q1;//queue which can store nodes.

Node* temp;

q1.push(root);

while(!q1.empty()) //looping while queue is empty.

{

temp=q1.front();

q1.pop();

cout<<temp->data<<" "; //printing the data.

if(temp->left)

q1.push(temp->left);

if(temp->right)

q1.push(temp->right);

}

}

int main()

{

Node *root=new Node(1); //Creating the Tree manually.

root->left=new Node(3);

root->right=new Node(4);

root->left->left=new Node(2);

root->right->right=new Node(6);

levelOrdertraversal(root); //printing each level..

}

Step-by-step explanation:

I have written the code of level order traversal of a binary tree.

I have used the approach using queue because it is efficient and widely used.This code will print all the nodes at same level.

I have created a class Node which contains the data of type int right and left pointer contains the address of next left and right node respectively.