Untitled

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Function to build a binary tree from a given array
TreeNode* buildTree(const vector<int>& nodes) {
    if (nodes.empty() || nodes[0] == -1) return NULL;

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

    while (i < nodes.size()) {
        TreeNode* current = q.front();
        q.pop();

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

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

    return root;
}

// Function to find the median of the nodes at the deepest level
double findDeepestLevelMedian(TreeNode* root) {
    if (!root) return 0.0;

    queue<TreeNode*> q;
    q.push(root);
    vector<int> deepestLevelNodes;

    while (!q.empty()) {
        int size = q.size();
        deepestLevelNodes.clear();  // Clear the previous level's nodes

        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            deepestLevelNodes.push_back(node->val);

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }

    sort(deepestLevelNodes.begin(), deepestLevelNodes.end());
    int n = deepestLevelNodes.size();

    // Find the median
    if (n % 2 == 1) {
        return deepestLevelNodes[n / 2];  // Odd number of elements
    } else {
        return (deepestLevelNodes[n / 2 - 1] + deepestLevelNodes[n / 2]) / 2.0;  // Even number of elements
    }
}

int main() {
    vector<int> nodes = {1, 2, 3, 4, 5, -1, 6, 7, 8};  // Example input
    TreeNode* root = buildTree(nodes);
    double median = findDeepestLevelMedian(root);
    cout << "Median of deepest level nodes: " << median << endl;
    return 0;
}