You need to implement the following functions for a binary search tree data structure:
BST(); // constructor, does what needs to be done when created
~BST(); // destructor, doest what needs to be done when destroyed
void insert(int v); // insert value v
string inorder(); // returns a string representing the values in the inorder traversal, separated by a space
There is only one private member "Node *root" in BST. The definition of Node is as follows:
struct Node {
int val;
int cnt; // occurence of value
Node *lc; // left child
Node *rc; // right child
Node(int v) : val(v), lc(nullptr), rc(nullptr) {} // init to null when created
};
Note that duplicate values may exist at the same time in the data structure
Q
OP_1
OP_2
...
OP_Q
Where Q is an integer representing the number of operations. Q lines follow.
OP_i is the i'th operation, and it may be one of the two following forms:
0 V
1
Where "0 V" will need you to insert V into the BST, and "1" needs you to print the inorder traversal. The operations has to be accomplished in the order they are given.
1 <= Q <= 2000
0 <= V <= 10^9
For each operation "1", print the inorder traversal in a line.