level order traversal of binary tree using queue (array implementation)

Question

I am getting unexpected output from my function that print tree nodes data in level order. I was following queue implementation of level order traversal without using STL library.

enter code here
#include <iostream>
using namespace std;

struct node{
int data;
node* left,*right;
};

int level_traversal(node* temp)
{
 node* arr[20];
 arr[0]=temp;
 int j=0;
 int i=0;
 while(arr[j] != NULL)
 {
  cout<<arr[j]->data<<" ";
  if(arr[j]->left != NULL)
  {
   i=i+1;
   arr[i]=arr[j]->left;
  }
  if(arr[j]->right != NULL)
  {
   i=i+1;
   arr[i]=arr[j]->right;
  }

  j=j+1;
 }

return 0;
}

node* node_creator(int value)
{
 node* temp=new node();
 temp->data=value;
 temp->left=NULL;
 temp->right=NULL;

 return temp;
}


int main() {
 node* root=node_creator(1);
 root->left=node_creator(2);
 root->right=node_creator(3);

 //left subtree
 root->left->left=node_creator(4);
 root->left->right=node_creator(5);

 level_traversal(root);
 return 0;
}

the error might be in implementation of function but i am not able to identify it

code_blocks output : 1 2 3 4 5 91537541

Lakshay Lakshay · Accepted Answer · 2020-08-05T14:40:45

while doing level order traversal or BFS it is important to maintain a NULL in queue as compiler will not be maintaining it for you . If you don't do so you will get unexpected outputs and segmentation faults at end of queue.

So the code can be improved by simply line 13) arr[1]=NULL;

and in both the if statements of level traversal function add) arr[i+1]=NULL;

level order traversal of binary tree using queue (array implementation)

1 Answers