Avoiding memory leaks and using pointers the right way in my binary search tree implementation - C++

Question

I'm learning C++ and I wanted to test my knowledge by implementing a Binary Search Tree using struct (I know, I’m using C++ I should use classes but I want to keep it simple).

As far as I know, all the functions work right, my problems are:

• Can I improve how I managed raw pointers?

  • (I know I should use unique_ptr but still...)

• Did I use new and delete the right way?

• Should I refactor some functions?

• In general, if I could improve something, just let me know!

Here's the complete code: https://gist.github.com/NeptuneLuke/f456c27a9c118d704c1734f7d4cb46c0

The main functions I'm concerned about are:

struct Node {
 int data;
 Node* left;
 Node* right;
};
void insert(Node* &root, int data) {
 // this implementation of a BST tree can not have duplicate nodes
 if(exist(root,data))
 return;
 if(root == nullptr) {
 
 root = new Node();
 root->data = data;
 root->left = nullptr;
 root->right = nullptr;
 }
 else {
 
 if(data < root->data) {
 insert(root->left,data);
 }
 else {
 insert(root->right,data);
 }
 }
}
void delete_tree(Node* &root) {
 if(root != nullptr) {
 
 delete_tree(root->left);
 delete_tree(root->right);
 delete root;
 root = nullptr;
 }
}
Node* delete_node(Node *root, int data) {
 
 if(root == nullptr || !exist(root,data)) {
 return nullptr;
 }
 else if(data < root->data) {
 root->left = delete_node(root->left,data);
 }
 else if (data > root->data) {
 root->right = delete_node(root->right,data);
 }
 else {
 // case 1 - no child
 if(root->left == nullptr && root->right == nullptr) {
 delete root;
 root = nullptr;
 }
 // case 2 - one child
 else if(root->left == nullptr) {
 Node *temp = root;
 root = root->right;
 delete temp;
 }
 // case 2 - one child
 else if(root->right == nullptr) {
 Node *temp = root;
 root = root->left;
 delete temp;
 }
 // case 3 - 2 children
 else {
 
 Node *temp = max_node(root->right);
 root->data = temp->data;
 root->right = delete_node(root->right,temp->data);
 }
 }
 return root; 
}

• Incomputable: "i know, i'm using C++ i should use classes but i want to keep it simple" do you know what classes and objects with correctly written constructors + destructors allow? As written, the code is just C. It is great that you can do it manually, but the big reason to use C++ comes from properly defining ownership rules and allowing compiler to take care of it, instead of overloading the user of the code with that responsibility.
• Neptune Luke: Yep, you're right. I thought i could still describe it as C++ cause i was using nullptr, new and delete, but yeah i'm not using anything about OOP and stuff.
• Neptune Luke: @JaneDoe Well this is just for learning purpose and i basically did it to try to see if i could code it. Not trying to say this is perfect or anything! I know i should/shouldn't use something, but i was trying to write the code the simplest way possible but also doing some "heavy lifting", cause i'm still learning the language.
• user555045: "I know I should use unique_ptr but still" - well maybe. Usually I prefer to have a Tree own all the nodes (which become an implementation detail of tree, not exposed), instead of the nodes owning each other and being out in the open. It depends what you want I suppose.
• Falco: From a purely algorithmic performance point of view you seem to traverse the tree multiple times on some operations. If you do exists() and then delete() the code is first searching the element to make sure it exists and afterwards searching again to delete it. I think this could be simplified to a single traversal of the tree (delete if exists and return null if it doesn't)

Answer 1

Given you are not using any actual C++ functionality, I’m going to think about this code as C code that uses new and delete instead of malloc and free.

I don’t see any obvious problems with memory allocation. If new fails in insert, the tree is still in a valid state.

---

About the API: insert and delete_tree take the root node pointer by reference, so they can modify it. You should do the same thing with delete_node, instead of returning the new root pointer. Do note that the caller can have multiple copies of the root node pointer, if one copy is modified, the others won’t. This is dangerous, and needs to be communicated clearly to the caller, in the form of API documentation.

It is better to have a tree object that holds the root pointer. The caller can then reference this object (struct instance) any number of times, and you’re free to change the root pointer at any time. When you’re ready to use actual C++ constructs, you’ll be able to delete the copy constructor and copy assignment operator, to ensure that the user doesn’t copy the object. You can then also call delete_tree in the destructor of the tree object, to prevent the user from forgetting to call this function.

---

About formatting: be consistent. You sometimes have an empty line after opening braces (in if or else statements), and sometimes don’t. I find this confusing, and try to look for a meaning...

---

This construct:

if(...) {
 return ...;
}
else { ... }

doesn’t need the else. You can often simplify code using early returns.

Answer 2

1. For C++, avoid using new/delete or c variants of memory allocation. Instead use std::make_unique.

2. Fix formatting, for example, consider using clang format, but there are others.

3. Consider setting the internal state of the object in the constructor:

root = new Node();
root->data = data;
root->left = nullptr;
root->right = nullptr;
=>
auto node = std::make_unique<Node>();
// all other things are set inside the Node ctor

4. Double-check your algorithm, use peer-review papers (for newer algorithms) or well-established books with the latest implementation. It took ~16 years to implement corectly a simple binary search algorithm.

5. Reading the comment and code

// this implementation of a BST tree can not have duplicate nodes
if(exist(root,data))
 return;

Start a comment with a capital letter (my personal preference) as it is easier to read, especially when you have more text in the comment. More importantly, the caller will not know if the element has been inserted or not. It may matter for some cashing systems - consider throwing an exception in this situation.

6. Logic in code can be simplified, avoid using if-elseif where possible:

if(root == nullptr || !exist(root,data)) {
 return nullptr;
}
else if(data < root->data) {
 root->left = delete_node(root->left,data);
}
=>
if(root == nullptr || !exist(root,data)) {
 return nullptr;
}
if(data < root->data) {
 root->left = delete_node(root->left,data);
}

7. You could consider using generics in c++, so that the algorithm can deal with other types of data, rather than int, but it is a bit opinionated and is subject to another question.

8. In real code, you'd want to document the branching conditions more, why are you having an if-else and why did you choose this specific boundaries.

• Raf: I'd argue against leaving out { }, in every project style guide I've encountered until now this is the default (expected to always use { and }, no if(a) expression;
• Graham: @Raf Seconded. Accidentally writing if(a) expression1; expression2; is a common enough bug and is really hard to find in review/debugging if the code is indented. Because it's so hard to find, all coding standards for safety-related code which I'm aware of mandate the use of braces after every conditional statement. MISRA at least considers this "required" rather than "advisory".
• Cris Luengo: Types in C and C++ are read right to left, Node*& is a reference to a pointer to Node. By taking the pointer by reference, the pointer can be updated to point to a different node.
• oleksii: Updated the code with the feedback