Understanding clang-tidy "DeadStores" and "NewDeleteLeaks" warnings

Question

I am relatively new to c++ programming, especially when dealing with OOP and pointers.

I am trying to implement a binary search tree, and here is the code I have

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;

  TreeNode() : val(0), left(NULL), right(NULL){};
  TreeNode(int v) : val(v), left(NULL), right(NULL){};
  TreeNode(int v, TreeNode* l, TreeNode* r) : val(v), left(l), right(r){};
};

void insert(TreeNode* root, TreeNode* v) {
  // inserts v into root, assuming values distinct
  if (root == NULL) {
    root = v; // L52
    return;
  }
  if (v == NULL) {
    return;
  }

  // traverse through tree using structure of BST
  TreeNode* cur = root;
  while (cur != NULL) {
    if (cur->val <= v->val) {
      if (cur->right == NULL) {
        cur->right = new TreeNode(v->val);
        break;
      }
      cur = cur->right;
    } else if (cur->val >= v->val) {
      if (cur->left == NULL) {
        cur->left = new TreeNode(v->val);
        break;
      }
      cur = cur->left;
    }
  }
}

void insert(TreeNode* root, int v) {
  insert(root, new TreeNode(v)); // L78
}

Now, I have two questions.

1. I realised that the L52 labelled above would not work. For example, if I do TreeNode* node = new TreeNode(5); TreeNode* empty = NULL; insert(empty, node);, it would not work. I am not sure how to fix this, so any help would be great.

2. Running clang-tidy on my code, I get the following slightly confusing warning:

./main.cpp:78:69: warning: Potential memory leak [clang-analyzer-cplusplus.NewDeleteLeaks]
void insert(TreeNode* root, int v) { insert(root, new TreeNode(v)); }
                                                                    ^
./main.cpp:132:3: note: Calling 'insert'
  insert(node, 3);
  ^
./main.cpp:78:51: note: Memory is allocated
void insert(TreeNode* root, int v) { insert(root, new TreeNode(v)); }
                                                  ^
./main.cpp:78:69: note: Potential memory leak
void insert(TreeNode* root, int v) { insert(root, new TreeNode(v)); }
                                                                    ^

I am not sure what this means, and whether it would be dangerous in any way. I found this from the LLVM docs and it seems that the temporary new TreeNode(v) is causing the problem. What is a better way to achieve what I want? Any further explanation or resources that I can read would be great.

Of course, any improvement to my bad coding style would be great as well ;) formatter saves the day.

Thank you!

Answer 1

Q1: How do I insert into a binary tree?

The main problem with the fragment:

void insert(TreeNode* root, TreeNode* v) {
  // inserts v into root, assuming values distinct
  if (root == NULL) {
    root = v; // L52
    return;
  }

is, although you have set a new value for root, root is a parameter to the insert function, and consequently is discarded when insert returns.

One way to fix this is to return the new value:

TreeNode*             // <-- changed return type
    insert(TreeNode* root, TreeNode* v) {
  // inserts v into root, assuming values distinct
  if (root == NULL) {
    root = v; // L52
    return root;      // <---- changed to return a value
  }

Every place insert returns (including at the end), return the value of root.

Then when you call insert, save the returned value:

TreeNode* root = ...;       // some existing tree
root = insert(root, 5);     // insert 5 and save the result

Now, the new value of root points to the tree that contains the inserted value.

Q2: What is clang-tidy complaining about?

Invoking new allocates memory. It must eventually be freed, otherwise (if this keeps happening) your program will eventually use all available memory. See the question When should I use the new keyword in C++?. Note especially this advice: "every time you type new, type delete."

Now, in this code as it stands, the problem is actually not the missing delete, it is the failure to return the updated root. clang-tidy realizes that, because the updated root is never returned, you can't possibly eventually delete it, so complains. Once you start returning that value, clang-tidy will wait to see what you do next.

As for what to do next, one simple approach is to regard TreeNode as owning its children, meaning it is obliged to delete them when it is destroyed. For example, first add a destructor method to TreeNode:

struct TreeNode {
  ...
  ~TreeNode() {        // <--- this is the destructor
    delete left;       // free left child (if not NULL)
    delete right;      // free right child
  }
};

Then in your code that manipulates trees, remember to delete the root node when finished:

TreeNode* root = NULL;
root = insert(root, 1);
root = insert(root, 2);
delete root;            // <--- free entire tree

A note about smart pointers

My suggestions above use a very direct, literal style of memory management, with explicit use of new and delete where needed. However, it is easy to forget to use delete, and tricky to get it right in the presence of exceptions. A commonly preferred alternative is to use smart pointers. But that's a somewhat advanced topic, so when just starting out, I recommend first getting comfortable with explicit new and delete, but keep in mind there is a better way when you're ready for it.