# Binary search tree with common operations

I trying to see if I implemented these operations correctly and if they could be optimized in any way. The implementations are just the typical implementations found online but I adjusted them to work with pointers. I did not find pseudocode for transplant, it was only described and I am unsure if it does what it is supposed to do. The tree works correctly for my small test cases, but I have not tried it with bigger data sets and operations. I purposely made the tree non-owning but if it were owning, left and right children could be unique_ptr's and parent be a Node*. I may implement that later.

class Node {
public:
Node(int key) : key(key) {}
Node* parent = nullptr;
Node* left = nullptr;
Node* right = nullptr;
int key;
};

class BinarySearchTree {
public:
BinarySearchTree() = default;
/// create tree from existing nodes
BinarySearchTree(Node* nodes[], unsigned n);
/// insert key into tree
void insert(Node* node);
/// remove node with key
void remove(Node* node);
/// find smallest node in subtree
Node* minimum(Node* node) const;
/// find largest node in subtree
Node* maximum(Node* node) const;
/// find successor of node
Node* successor(Node* node) const;
/// find predecessor of node
Node* predecessor(Node* node) const;
/// replace subtree at a with subtree at b
void transplant(Node* a, Node* b);
/// find node with key
Node* find(int key) const;
/// find kth smallest element
Node* kth(unsigned k) const;
/// write data to stream
friend std::ostream& operator<<(std::ostream& out, const BinarySearchTree& tree);

private:
/// helper method to initialize tree
void build_bst(BinarySearchTree& tree, Node* nodes[], unsigned n);
/// helper method for find
Node* find(int key, Node* subtree) const;
/// pointer to the root
Node* root = nullptr;
};

void BinarySearchTree::build_bst(BinarySearchTree& tree, Node* nodes[], unsigned n) {
if (n == 0) return;
tree.insert(nodes[n/2]);
build_bst(tree, nodes, n/2);
build_bst(tree, nodes + n/2 + 1, n - 1 - n/2);
}

BinarySearchTree::BinarySearchTree(Node* nodes[], unsigned n) {
build_bst(*this, nodes, n);
}

void BinarySearchTree::insert(Node* node) {
Node* parent = nullptr;
Node* child = root;

while (child) {
parent = child;
if (node->key < child->key)
child = child->left;
else
child = child->right;
}

node->parent = parent;
if (!parent) {
root = node;
} else if (node->key < parent->key) {
parent->left = node;
} else {
parent->right = node;
}
}

void BinarySearchTree::remove(Node* node) {
if (!node->left && !node->right) {
// special case where only node is root
if (node->parent) {
// remove leaf node
if (node->parent->key < node->key) {
node->parent->right = nullptr;
} else {
node->parent->left = nullptr;
}
} else {
root = nullptr;
}
node->parent = nullptr;
} else if (!node->left && node->right) {
// no left child
transplant(node, node->right);
} else if (node->left && !node->right) {
// no right child
transplant(node, node->left);
} else {
// check if min = successor(node)
Node* min = successor(node);
if (min->parent != node) {
transplant(min, min->right);
min->right = node->right;
min->right->parent = min;
}
transplant(node, min);
min->left = node->left;
min->left->parent = min;
}
}

Node* BinarySearchTree::minimum(Node* node) const {
Node* parent = nullptr;
Node* child = node;

while (child) {
parent = child;
child = child->left;
}

return parent;
}

Node* BinarySearchTree::maximum(Node* node) const {
Node* parent = nullptr;
Node* child = node;

while (child) {
parent = child;
child = child->right;
}

return parent;
}

Node* BinarySearchTree::successor(Node* node) const {
if (node->right) {
// find minimum of right subtree
return minimum(node->right);
} else {
// find parent of furthest node through right branches
Node* iter = node;
while (iter->parent) {
if (iter->parent->key < iter->key) {
iter = iter->parent;
} else {
break;
}
}

// will return nullptr if no successor
return iter->parent;
}
}

Node* BinarySearchTree::predecessor(Node* node) const {
if (node->left) {
return maximum(node->left);
} else {
// find parent of furthest node through left branches
Node* iter = node;
while (iter->parent) {
if (iter->key < iter->parent->key) {
iter = iter->parent;
} else {
break;
}
}

// will return nullptr if no predecessor exists
return iter->parent;
}
}

void BinarySearchTree::transplant(Node* a, Node* b) {
if (b->parent->key < b->key) {
b->parent->right = nullptr;
} else {
b->parent->left = nullptr;
}

b->parent = a->parent;

// special case when a is root
if (a->parent) {
if (a->parent->key < a->key) {
a->parent->right = b;
} else {
a->parent->left = b;
}
} else {
root = b;
}
}

Node* BinarySearchTree::find(int key) const {
return find(key, root);
}

Node* BinarySearchTree::find(int key, Node* subtree) const {
if (!subtree) return nullptr;
if (subtree->key < key)
return find(key, subtree->right);
else if (subtree->key > key)
return find(key, subtree->left);
else
return subtree;
}

Node* BinarySearchTree::kth(unsigned k) const {
Node* kth = minimum(root);
for (unsigned i = 0; i < k-1; ++i) {
if (kth)
kth = successor(kth);
else
return kth;
}

// returns nullptr if kth element does not exist
return kth;
}

/// in-order traversal/print
std::ostream& operator<<(std::ostream& out, const Node& node) {
if (node.left)
out << *node.left;
out << node.key << ' ';
if (node.right)
out << *node.right;
return out;
}

/// print the entire tree
std::ostream& operator<<(std::ostream& out, const BinarySearchTree& tree) {
if (!tree.root) return out;
return out << *tree.root;
}


# Good stuff

• Consistent indentation
• /// documenting comments (I applaud to that)
• What it does first, how it does it last
(although I personally prefer inline bodies, this is nice example of the separation being done right)

# Design

What could be the reason to have the nodes exposed and not owned?
The tree should, in my opinion, accept and expose only values and be a template:

template<class T>
class BinarySearchTree {
struct Node {
std::unique_ptr<Node> left = nullptr;
std::unique_ptr<Node> right = nullptr;
T key;
Node(T key) : key(std::move(key)) {}
};
public:
BinarySearchTree(std::initializer_list<T> init);


You should notice that:

1. It uses std::unique_ptr because there is simply no excuse now! If you, for whatever reason, need something like Node* then it should rather be iterator or node handle (C++17).
2. It has constructor accepting std::initializer_list to enable construction like BinarySearchTree<int>{1,2,3}
3. No parent inside node. I will elaborate this a bit more:

I can understand why you did this, because I have done it during my first exam and it was not received well by the teacher. You can use stacks tracking the path from root to current node (maybe make it part of the iterator if needed) to implement every exposed operation. I know it is easier to have the parent in the node, but it should not be there.

## Balancing the tree

You have provided constructor (BinarySearchTree(Node* nodes[], unsigned n) using build_bst(BinarySearchTree& tree, Node* nodes[], unsigned n)) that will produce well-balanced tree if the input array is sorted (should probably check and sort if needed), but did not make the tree read-only, which means, that you should provide some means of rebalancing the tree. Try reading about Red-Black Tree (and maybe AVL Tree as alternative).

Personal story: The purpose of the exam was to show understanding of pointers to handle joining two trees or heaps. The teacher could not imagine that somebody would even think about optimal solution... ehm, I did, and received some unwanted attention for the rest of my studies for doing so while helping myself using that parent pointer instead of three stacks - there was simply not enough time to pull this out... and I was not supposed to even think about such solution, you know :D I hope you now understand that I am not stressing the removal of parent too much :)

• Thanks for the response. This was for my data structures class and we were expected to have the parent pointer. I have modified this code further and I could try implementing without the parent pointer Commented Sep 28, 2018 at 19:43
• If the only purpose of the review was to check the code before you submit it to the teacher, then, well, it looks good for the level I am assuming you are at. You can test insert and remove a bit more, to be sure, but I did not spot any obvious flaw in the implementation.
– user52292
Commented Sep 28, 2018 at 20:12
• In your personal story, the parent pointer implementation was the optimal solution or wasn’t? I can see how it saves memory. I’m also implementing an avl right now Commented Sep 28, 2018 at 21:04
• @BradyDean: The parent pointer did not change the speed, stack would produce same Big-O (some logarithm in it probably). I have used the pointer to even be able to write it ON PAPER IN TIME. The teacher expected something less-optimal (maybe quadratic complexity) but much easier to write (just tear the nodes from one tree/heap one at a time and put them in the bigger one). I was the only one to even try something smarter/faster. But adding that pointer to the node to make it easier to implement just made the teacher, ehm, mad at me.
– user52292
Commented Sep 28, 2018 at 21:11
• Our professor haven’t even mentioned implementations without the parent pointer and hasn’t talked about using a stack when iterating through. I like the idea tho Commented Sep 28, 2018 at 21:14