Level order traversal of binary search tree

Question

I was trying to implement level order traversal of binary search tree using linked list implementation of queue.

I have checked the binary search tree implementation and it is fine. The linked list implementation of queue is also correct. Here i am trying to visit the node and enqueue its children to the queue. and then use the pop function to actually visit the node.

This is being done via a recursive call in the end. When i run the following code i am getting the output in different order.

// Trees
#include <stdio.h>
#include <stdlib.h>

//Node declaration for binary search tree

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


// LINKED LIST BASED IMPLEMENTATION OF QUEUE

struct qnode 
{
struct node *data;
struct qnode *next;
};



struct qnode *head = NULL;


void insertq (struct node *);   //This function enqueue node in the queue.

struct node *pop ();        // dequeue  function

//The function declaration for level order traversal.

void leorder ();



struct node *make (int);
struct node *insert (struct node *, int);



void 
main () 
{



struct node *root = NULL;


root = insert (root, 10);


root = insert (root, 9);


root = insert (root, 8);


root = insert (root, 5);


root = insert (root, 2);


root = insert (root, 4);


root = insert (root, 3);


root = insert (root, 6);


root = insert (root, 7);


root = insert (root, 1);


insertq (root);     //Insertion of first root.


leorder ();


} 

//The program that makes nodes for the bst.

struct node* make(int x){
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->data = x;
temp->left = NULL;
temp->right = NULL;

return temp;
};




//The node insertion function.(BINARY SEARCH TREE)

struct node* insert(struct node* root,int x){
if(root == NULL){
    root = make(x);
}
else{
if(x <= root->data){
    root->left = insert(root->left,x);
}

else{
    root->right = insert(root->right,x);
}}
return root;
}




// This function will insert node in the queue.

void insertq(struct node* x){

if(head == NULL){
struct qnode* temp = (struct qnode*)malloc(sizeof(struct qnode));
temp->data = x;
temp->next = NULL;
head = temp;
}
else{
struct qnode* temp = (struct qnode*)malloc(sizeof(struct qnode));
temp->data = x;
temp->next = head;
head = temp;
}
}

struct node* pop(){
struct node* r;
if(head == NULL){
    return NULL;
}
else{
 struct qnode* pt;
 pt = head;
 head = head->next;
 r = pt->data;
 free(pt);
 return r;
}
}


// dequeue function.

struct node* pop(){
struct node* r;
if(head == NULL){
    return NULL;
}
else{
 struct qnode* pt;
 pt = head;
 head = head->next;
 r = pt->data;
 free(pt);
 return r;
}
}



// Function to print tree in level order.

void leorder(){
struct node* popped;
popped = pop();
printf("%d ",popped->data);
if(popped != NULL){
    if(popped->left != NULL){
        insertq(popped->left);
    }

    if(popped->right != NULL){
        insertq(popped->right);
    }
    leorder();
}
}

Tip: Standard terminology is "enqueue" and "dequeue", not "insertq" and "pop" — ikegami
Tip: Both the "then" and the "else" part of the if statement in inserq are the same. No need for an if statement. — ikegami

ikegami ikegami · Accepted Answer · 2019-10-16T19:35:03

Right now, you insert at the head, and you remove at the head. This means you have a stack (last in, first out), not a queue (first in, first out).

Add a tail pointer, and remove from the opposite end that you add. If you add at the head, remove from the tail, or vice-versa.

Level order traversal of binary search tree

1 Answers