Write a C++ program to perform the following operations: 1. It first prompts the

Question

Write a C++ program to perform the following operations: 1. It first prompts the user to input a sequence of integers to construct a binary search tree, in which each node has an additional field leftSize. The definition of leftSize is the same as given in the textbook. 2. Print out the values of leftSize by level-order traversal, i.e. level by level and from left to right in each level. 3. After the tree is constructed, allow a user to submit the following queries: The average of the SMALLEST k elements. If k exceeds the number of elements in the tree, return -1 The average of the LARGEST k elements. Ifkexceeds the number of elements in the tree, return -1 The median element of the entire BST. If the number of elements in the tree is even, return the average of the two median elements.

Explanation / Answer

#include <iostream>

#include <queue>

using namespace std;

struct Node

{

    int data;

    Node *left;

    Node *right;

};

Node *newNode(int data)

{

    Node *node = new Node;

    node->data = data;

    node->right = node->left = NULL;

    return node;

}

void printSpecificLevelOrder(Node *root)

{

    if (root == NULL)

        return;

    cout << root->data;

    if (root->left != NULL)

      cout << " " << root->left->data << " " << root->right->data;

    if (root->left->left == NULL)

        return;

    queue <Node *> q;

    q.push(root->left);

    q.push(root->right);

    Node *first = NULL, *second = NULL;

    while (!q.empty())

    {

       // Pop two items from queue

       first = q.front();

       q.pop();

       second = q.front();

       q.pop();

       cout << " " << first->left->data << " " << second->right->data;

       cout << " " << first->right->data << " " << second->left->data;

       if (first->left->left != NULL)

       {

           q.push(first->left);

           q.push(second->right);

           q.push(first->right);

           q.push(second->left);

       }

    }

}

int main()

{

    Node *root = newNode(1);

    root->left        = newNode(2);

    root->right       = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->right->left = newNode(6);

    root->right->right = newNode(7);

    root->left->left->left = newNode(8);

    root->left->left->right = newNode(9);

    root->left->right->left = newNode(10);

    root->left->right->right = newNode(11);

    root->right->left->left = newNode(12);

    root->right->left->right = newNode(13);

    root->right->right->left = newNode(14);

    root->right->right->right = newNode(15);

    root->left->left->left->left = newNode(16);

    root->left->left->left->right = newNode(17);

    root->left->left->right->left = newNode(18);

    root->left->left->right->right = newNode(19);

    root->left->right->left->left = newNode(20);

    root->left->right->left->right = newNode(21);

    root->left->right->right->left = newNode(22);

    root->left->right->right->right = newNode(23);

    root->right->left->left->left = newNode(24);

    root->right->left->left->right = newNode(25);

    root->right->left->right->left = newNode(26);

    root->right->left->right->right = newNode(27);

    root->right->right->left->left = newNode(28);

    root->right->right->left->right = newNode(29);

    root->right->right->right->left = newNode(30);

    root->right->right->right->right = newNode(31);

    cout << "Specific Level Order traversal of binary tree is ";

    printSpecificLevelOrder(root);

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.