#include <iostream>
#include <queue>
using namespace std;

// Binary Tree Node
struct Node {
    int data;
    Node* left;
    Node* right;
};

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = new Node();
    if (!newNode) {
        cout << "Memory error\n";
        return NULL;
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function to insert a node in the tree using level-order traversal
Node* levelOrderInsertion(Node* root, int value) {
    if (root == NULL) {
        root = createNode(value);
        return root;
    }
    
    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        
        if (temp->left == NULL) {
            temp->left = createNode(value);
            break;
        } else {
            q.push(temp->left);
        }
        
        if (temp->right == NULL) {
            temp->right = createNode(value);
            break;
        } else {
            q.push(temp->right);
        }
    }
    
    return root;
}

// Depth-First Search (DFS) Traversal
void dfsTraversal(Node* root) {
    if (root == NULL) {
        return;
    }
    
    cout << root->data << " ";
    dfsTraversal(root->left);
    dfsTraversal(root->right);
}

// Breadth-First Search (BFS) Traversal
void bfsTraversal(Node* root) {
    if (root == NULL) {
        return;
    }
    
    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        
        cout << temp->data << " ";
        
        if (temp->left != NULL) {
            q.push(temp->left);
        }
        
        if (temp->right != NULL) {
            q.push(temp->right);
        }
    }
}

// Function to delete leaf nodes using level-order traversal
Node* levelOrderDeletion(Node* root) {
    if (root == NULL) {
        return NULL;
    }
    
    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        
        if (temp->left != NULL) {
            if (temp->left->left == NULL && temp->left->right == NULL) {
                delete temp->left;
                temp->left = NULL;
            } else {
                q.push(temp->left);
            }
        }
        
        if (temp->right != NULL) {
            if (temp->right->left == NULL && temp->right->right == NULL) {
                delete temp->right;
                temp->right = NULL;
            } else {
                q.push(temp->right);
            }
        }
    }
    
    return root;
}

int main() {
    Node* root = NULL;
    
    // Level-order insertion
    root = levelOrderInsertion(root, 1);
    root = levelOrderInsertion(root, 2);
    root = levelOrderInsertion(root, 3);
    root = levelOrderInsertion(root, 4);
    root = levelOrderInsertion(root, 5);
    
    cout << "DFS Traversal: ";
    dfsTraversal(root);
    cout << endl;
    
    cout << "BFS Traversal: ";
    bfsTraversal(root);
    cout << endl;
    
    // Level-order deletion of leaf nodes
    root = levelOrderDeletion(root);
    
    cout << "DFS Traversal after deletion: ";
    dfsTraversal(root);
    cout << endl;
    
    return 0;
}