give me c++ code Problem Statement: You are a data scientist working for an ancient…
- User
give me c++ code Problem Statement: You are a data scientist working for an ancient library that stores its scrolls in a binary tree structure, where each node represents a scroll with historical data. The scrolls at odd-numbered levels are older and should be accessed in descending order to preserve the reading flow, while the scrolls at even-numbered levels are newer and should be accessed in ascending order. The librarian has tasked you with a challenge: Depending on the type of analysis you are doing, you need to either retrieve the scrolls from odd levels or from even levels, following the proper order for each. Your job is to implement a program that can build this tree and then allow the librarian to choose whether to print the scrolls at odd or even levels. Problem:
- First, you will be given a number 'n', which represents the number of scrolls in the library.
- Next, you will receive 'n' integers, which are the unique historical values of the scrolls to be inserted into the binary search tree.
- Finally, the librarian will ask you to either print the scrolls at "odd levels in descending order or even levels in ascending order. Input Format: The first input is an integer n representing the number of scrolls (nodes) to be inserted. The second input is a series of n integers representing the historical values of the scrolls. The third input is either the word "odd" or "even", indicating which levels of scrolls to print. Output Format: If "odd" is chosen, print the values of the scrolls at odd levels in descending order. • If "even" is chosen, print the values of the scrolls at even levels in ascending order.Sample Test Cases Test Case 1: Expected Output: 6 12 16 11 18 22 17
odd 18-12- Test Case 2: Expected Output: 4 13 12 10 11 even 11-12-
- Assistant
#include <iostream> #include <vector> #include <queue> #include <algorithm> struct Node { int data; Node* left; Node* right; }; // Function to create a new BST node Node* createNode(int data) { Node* newNode = new Node(); if(!newNode) { return nullptr; } newNode->data = data; newNode->left = newNode->right = nullptr; return newNode; } // Function to insert a new node into the BST Node* insertNode(Node* root, int data) { if(root == nullptr) { root = createNode(data); return root; } if(data < root->data) { root->left = insertNode(root->left, data); } else { root->right = insertNode(root->right, data); } return root; } // Function to collect nodes at odd or even levels void collectNodesAtLevels(Node* root, const std::string& command, std::vector<int>& values) { if(root == nullptr) return; std::queue<std::pair<Node*, int>> q; // Queue for level order traversal q.push(std::make_pair(root, 1)); // Start with level 1 while(!q.empty()) { Node* current = q.front().first; int level = q.front().second; q.pop(); // Check if the level is odd or even as required if((command == "odd" && level % 2 == 1) || (command == "even" && level % 2 == 0)) { values.push_back(current->data); } // Enqueue left and right children with incremented level if(current->left) { q.push(std::make_pair(current->left, level + 1)); } if(current->right) { q.push(std::make_pair(current->right, level + 1)); } } } // Function to delete the BST and free memory void deleteTree(Node* node) { if(node == nullptr) return; deleteTree(node->left); deleteTree(node->right); delete node; } int main() { int n; std::cin >> n; Node* root = nullptr; // Insert scrolls into the BST for(int i = 0; i < n; ++i) { int val; std::cin >> val; root = insertNode(root, val); } std::string command; std::cin >> command; std::vector<int> values; // Collect scrolls at the required levels collectNodesAtLevels(root, command, values); // Sort the values based on the required order if(command == "odd") { std::sort(values.begin(), values.end(), std::greater<int>()); } else if(command == "even") { std::sort(values.begin(), values.end()); } // Print the scrolls with "-" separator for(int val : values) { std::cout << val << "-"; } std::cout << std::endl; // Clean up memory deleteTree(root); return 0; }Example Usage:
Input Test Case 1:
6 12 16 11 18 22 17 oddOutput:
18-12-Input Test Case 2:
4 13 12 10 11 evenOutput:
11-12-Explanation:
-
Building the BST:
- The BST is constructed by inserting the given scroll values one by one.
- For example, with the input
6 12 16 11 18 22 17, the BST will have nodes arranged according to the binary search tree property.
-
Collecting Nodes at Specified Levels:
- The function
collectNodesAtLevelsperforms a level-order traversal of the BST. - It keeps track of the current level and collects the scroll values that are at the specified odd or even levels.
- The function
-
Sorting and Printing Scrolls:
- The collected scrolls are sorted in the required order:
- Odd levels: Descending order.
- Even levels: Ascending order.
- The scrolls are then printed, separated by dashes (
-), to preserve the reading flow.
- The collected scrolls are sorted in the required order:
Note: This program reads input from the standard input and writes output to the standard output. Ensure that the inputs are provided in the correct format when running the program.
-