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 a node with value v if v is not in the tree
void erase(int v); // delete a node with value v if v is in the tree
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;
Node *lc; // left child
Node *rc; // right child
Node(int v) : val(v), lc(nullptr), rc(nullptr) {} // init to null when created
};
Note that depending on your implementation, the relation between nodes of your BST and those of others' may be different, but it's alright because the inorder will be the same.
***UPDATE***
In case you have no idea how to implement `erase`, here's a blueprint for a simple algorithm:
// A recursive function to delete v from subtree cur, where par is parent of cur
void dfs(Node *cur, Node *par, int v) {
if (cur is empty) return; // obviously...
if (cur is the node you want to delete) {
if (cur has both left and right children) {
Set par->lc or par->rc to cur->lc depending on the relation between par and cur;
(the node with the largest value in subtree rooted at cur->lc)->rc = cur->rc;
} else {
If you know what's happening so far, you should know what goes here
}
remove cur from existence;
dfs to either cur->lc or cur->rc depending on whether v < cur->val is true;
}
In case you do spot a possible corner case in this implementation, you may consider taking care of it on your own, or having an extra node for infinity in the beginning (if you see how this helps).
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 three following forms:
0 V
1 V
2
Where "0 V" will need you to insert V into the BST (if V exists already, you should ignore this), "1 V" needs you to delete V in the BST (if V does not exist, ignore this), and "2" 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 "2", print the inorder traversal in a line.