In this question, you have to perform add and delete on binary search tree.
Note that:
- When deleting a node which still have 2 children, take the inorder successor (smallest node of the
right sub tree of that node) to replace it.
- When adding a node which has the same value as parent node, add it in the left sub tree.
//Helping functions
Node* addRec(Node* root, T value) {
if (root == nullptr) {
return new Node(value);
if (value <= root->value) {
root->pLeft = addRec(root->pLeft, value);
} else {
root->pRight = addRec(root->pRight, value);
return root;
void add(T value){
this->root = addRec(this->root, value);
Node* minValueNode(Node* node) {
Node* current = node;
while (current && current->pLeft != nullptr) {
current = current->pLeft;
return current;
}
Node* deleteRec(Node* root, T value) {
if (root == nullptr) {
return root;
if (value < root->value) {
root->pLeft = deleteRec(root->pLeft, value);
else if (value > root->value) {
root->pRight = deleteRec(root->pRight, value);
else {
if (root->pLeft == nullptr) {
Node* temp = root->pRight;
delete root;
return temp;
} else if (root->pRight == nullptr) {
Node* temp = root->pLeft;
delete root;
return temp;
Node* temp = minValueNode(root->pRight);
root->value = temp->value;
root->pRight = deleteRec(root->pRight, temp->value);
}
return root;
void deleteNode(T value){
//TODO
this->root = deleteRec(this->root, value);
Given class BinarySearchTree, you need to finish method getMin()
and getMax() in this question.
T getMinRec(Node* root) {
if (root == nullptr) {
throw runtime_error("Tree is empty");
while (root->pLeft != nullptr) {
root = root->pLeft;
return root->value;
T getMaxRec(Node* root) {
if (root == nullptr) {
throw runtime_error("Tree is empty");
while (root->pRight != nullptr) {
root = root->pRight;
}
return root->value;
T getMin() {
return getMinRec(root);
T getMax() {
return getMaxRec(root);
Given class BinarySearchTree, you need to finish method find(i) to check
whether value i is in the tree or not; method sum(l,r) to calculate sum of all all
elements v in the tree that has value greater than or equal to l and less than or
equal to r.
bool findRec(Node* root, T i) {
if (root == nullptr) {
return false; // Value not found
if (root->value == i) {
return true; // Value found
} else if (i < root->value) {
return findRec(root->pLeft, i);
} else {
return findRec(root->pRight, i);
bool find(T i) {
return findRec(root, i);
T sumRec(Node* root, T l, T r) {
if (root == nullptr) {
return 0;
T sum = 0;
if (root->value >= l && root->value <= r) {
sum += root->value;
if (root->value >= l) {
sum += sumRec(root->pLeft, l, r);
if (root->value <= r) {
sum += sumRec(root->pRight, l, r);
return sum;
T sum(T l, T r) {
return sumRec(root, l, r);
Class BSTNode is used to store a node in binary search tree, described on the following:
Where val is the value of node, left and right are the pointers to the left node and right node of it,
respectively. If a repeated value is inserted to the tree, it will be inserted to the left subtree.
Also, a static method named createBSTree is used to create the binary search tree, by iterating the
argument array left-to-right and repeatedly calling addNode method on the root node to insert the
value into the correct position. For example:
int arr[] = {0, 10, 20, 30};
auto root = BSTNode::createBSTree(arr, arr + 4);
vector<int> levelAlterTraverse(BSTNode* root) {
vector<int> result;
if (root == nullptr) return result;
deque<BSTNode*> nodeDeque;
nodeDeque.push_back(root);
bool leftToRight = true;
while (!nodeDeque.empty()) {
int size = nodeDeque.size();
vector<int> currentLevel(size);
for (int i = 0; i < size; ++i) {
BSTNode* currentNode;
if (leftToRight) {
currentNode = nodeDeque.front();
nodeDeque.pop_front();
if (currentNode->left != nullptr) nodeDeque.push_back(currentNode->left);
if (currentNode->right != nullptr) nodeDeque.push_back(currentNode->right);
} else {
currentNode = nodeDeque.back();
nodeDeque.pop_back();
if (currentNode->right != nullptr) nodeDeque.push_front(currentNode->right);
if (currentNode->left != nullptr) nodeDeque.push_front(currentNode->left);
currentLevel[i] = currentNode->val;
result.insert(result.end(), currentLevel.begin(), currentLevel.end());
leftToRight = !leftToRight; // Alternate the direction
return result;
Request: Implement function:
int rangeCount(BTNode* root, int lo, int hi);
Where root is the root node of given binary search tree (this tree has between 0 and 100000
elements), lo and hi are 2 positives integer and lo ≤ hi. This function returns the number of all
nodes whose values are between [lo, hi] in this binary search tree.
int rangeCount(BTNode* root, int lo, int hi) {
if (root == NULL) return 0;
if (root->val > hi) return rangeCount(root->left, lo, hi);
if (root->val < lo) return rangeCount(root->right, lo, hi);
return 1 + rangeCount(root->left, lo, hi) + rangeCount(root->right, lo, hi);
Request: Implement function:
int singleChild(BSTNode* root);
Where root is the root node of given binary search tree (this tree has between 0 and 100000
elements). This function returns the number of single children in the tree.
int singleChild(BSTNode* root) {
if (root == NULL) return 0;
int count = 0;
if ((root->left != NULL && root->right == NULL) ||
(root->left == NULL && root->right != NULL)) {
count = 1;
return count + singleChild(root->left) + singleChild(root->right);
}
int kthSmallest(BSTNode* root, int k) {
stack<BSTNode*> nodes;
BSTNode* current = root;
int count = 0;
while (current != nullptr || !nodes.empty()) {
while (current != nullptr) {
nodes.push(current);
current = current->left;
current = nodes.top();
nodes.pop();
count++;
if (count == k) {
return current->val;
current = current->right;
return INT_MIN;
BSTNode* subtreeWithRange(BSTNode* root, int lo, int hi) {
if (root == NULL) return NULL;
root->left = subtreeWithRange(root->left, lo, hi);
root->right = subtreeWithRange(root->right, lo, hi);
if (root->val < lo) {
BSTNode* rChild = root->right;
delete root;
return rChild;
if (root->val > hi) {
BSTNode* lChild = root->left;
delete root;
return lChild;
return root;
