#include <stdio.h>
#include <stdlib.h>
 
// Structure for BST Node
struct Node {
    int data;
    struct Node *left, *right;
};
 
// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}
 
// Function to insert a new node into BST
struct Node* insert(struct Node* root, int value) {
    if (root == NULL)
        return createNode(value);
 
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);
 
    return root;
}
 
// Queue node for level order traversal
struct QueueNode {
    struct Node* data;
    struct QueueNode* next;
};
 
// Queue structure
struct Queue {
    struct QueueNode *front, *rear;
};
 
// Function to create an empty queue
struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}
 
// Enqueue function
void enqueue(struct Queue* q, struct Node* node) {
    struct QueueNode* temp = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    temp->data = node;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}
 
// Dequeue function
struct Node* dequeue(struct Queue* q) {
    if (q->front == NULL)
        return NULL;
 
    struct QueueNode* temp = q->front;
    struct Node* node = temp->data;
    q->front = q->front->next;
 
    if (q->front == NULL)
        q->rear = NULL;
 
    free(temp);
    return node;
}
 
// Check if queue is empty
int isEmpty(struct Queue* q) {
    return q->front == NULL;
}
 
// Level Order Traversal function
void levelOrder(struct Node* root) {
    if (root == NULL)
        return;
 
    struct Queue* q = createQueue();
    enqueue(q, root);
 
    printf("Level Order Traversal: ");
    while (!isEmpty(q)) {
        struct Node* current = dequeue(q);
        printf("%d ", current->data);
 
        if (current->left != NULL)
            enqueue(q, current->left);
        if (current->right != NULL)
            enqueue(q, current->right);
    }
    printf("\n");
}
 
int main() {
    struct Node* root = NULL;
 
    // Construct the BST
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);
 
    // Display traversals
    levelOrder(root);
 
    return 0;
}