#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    // Initializer list avoids the val = val shadowing bug
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Builds a binary tree from level-order array input (-1 denotes NULL)
TreeNode* buildTree(const vector<int>& nodes) {
    if (nodes.empty() || nodes[0] == -1) return nullptr;

    TreeNode* root = new TreeNode(nodes[0]);
    queue<TreeNode*> q;
    q.push(root);

    int i = 1;
    while (!q.empty() && i < nodes.size()) {
        TreeNode* curr = q.front();
        q.pop();

        // Left child
        if (i < nodes.size() && nodes[i] != -1) {
            curr->left = new TreeNode(nodes[i]);
            q.push(curr->left);
        }
        i++;

        // Right child
        if (i < nodes.size() && nodes[i] != -1) {
            curr->right = new TreeNode(nodes[i]);
            q.push(curr->right);
        }
        i++;
    }
    return root;
}

// Inorder traversal to print values
void printInorder(TreeNode* root) {
    if (!root) return;
    printInorder(root->left);
    cout << root->val << " ";
    printInorder(root->right);
}

// Level-order traversal (BFS) to print level by level
void printLevelOrder(TreeNode* root) {
    if (!root) {
        cout << "Empty tree\n";
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* curr = q.front();
        q.pop();
        cout << curr->val << " ";
        if (curr->left) q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
    cout << "\n";
}

int main() {
    // -------------------------------------------------------------
    // Option 1: Direct Vector Input (LeetCode style: [1, 2, 3, -1, 4])
    // -------------------------------------------------------------
    vector<int> sample = {1, 2, 3, -1, 4, 5, 6};
    TreeNode* root1 = buildTree(sample);

    cout << "Tree 1 Inorder: ";
    printInorder(root1);
    cout << "\nTree 1 Level Order: ";
    printLevelOrder(root1);

    // -------------------------------------------------------------
    // Option 2: Dynamic input from cin
    // Input format: N followed by N integers (use -1 for NULL)
    // -------------------------------------------------------------
    /*
    int n;
    if (cin >> n) {
        vector<int> arr(n);
        for (int i = 0; i < n; i++) cin >> arr[i];
        TreeNode* root2 = buildTree(arr);
        
        cout << "Custom Tree Inorder: ";
        printInorder(root2);
        cout << "\n";
    }
    */

    return 0;
}