CODEWITHSUNDEEP
c++
Invictus
Invictus

Reputation: 4338

Will this piece of code for binary tree cause any issue?

I have written a piece of code and it runs fine on my system. I am not having any issue, but I have a few concerns, which I am listing below. I would like to know if there is a real issue.

# include <iostream>
# include <stdio.h>
# include<conio.h>
using namespace std;

struct tree
{
  int data;
  struct tree * left;
  struct tree * right;
};

struct tree * insert(struct tree * root,int value)
{
     if(root==NULL)
     {
      struct tree *node=(struct tree *)malloc(sizeof(struct tree));
      node->data = value;
      node->left=NULL;
      node->right=NULL;
      return node;
     }
     else if(root->data > value)
       root->left=insert(root->left,value);
     else {
       root->right=insert(root->right,value);
       /*return root;*/  // code works fine for me without this return
     }
}

void display(struct tree * root)
{ 
    if (root!=NULL)
    {
      display(root->left);
      cout << "value is : " << root->data << " \n";
      display(root->right);
    }
}

int main()
{
   struct tree* root=NULL;
   root=insert(root,8);
   insert(root,6);
   insert(root,5);
   insert(root,2);
   insert(root,1);
   insert(root,7);
   insert(root,15);
   display(root);
   delete root;
   getch();
}

My code works fine without the return root statement in the insert function. The thing that worries me is that I am not returning anything during the recursive calls between the creation of the root and the insertion of the final element in this recursive function. But things are still all fine for me.

Can this become a problem in the future in more complex coding scenarios?

Upvotes: 0

Views: 226

Answers (5)

unludo
unludo

Reputation: 5010

If you are not sure, then test it :-). TDD, BDD is a very good way to code (the only good way?). There are tons of tools to do that in c++. I recently used google test which is good and easy.

http://code.google.com/p/googletest/

Each test corresponds to a requirement that you fulfill by writing the code. This is called Behavior Driven Development. Learn that and you will greatly improve your skills.

And for memory leaks, use a tool like valgrind ( http://valgrind.org/ ), it checks it for you.

Upvotes: 1

Chasefornone
Chasefornone

Reputation: 757

I am not very sure your code can be compiled successfully without any warnings, because you declare the insert function to return a pointer, but not all control paths return a value (at least on my machine with Visual Studio 2008 installed). The code may also cause a memory leak, because you just delete the root node, while all its children are still alive. There are a lot of articles about how to write a binary search tree in C++. Hope it helps!

Upvotes: 0

Thomas Eding
Thomas Eding

Reputation: 1

Never delete data that was malloced. Always use free instead. UB will result otherwise.

Upvotes: 1

Sufian Latif
Sufian Latif

Reputation: 13356

This code works fine because insert returns something when a new node is created, and returns the pointer to the new node to its parent. It's not necessary to return the parent's pointer to the grand-parent - the grand-parent already has the parent's pointer. So the insertion is correctly done.

One more thing to notice: your code is prone to memory leak. The statement delete root; in main is not enough to free up all the allocated memory. To delete all the malloc-ed memory you'll need to a recursive function very similar to insert: when you pass a node * to it, the function will free the left and right children first, then free itself. It's just like the post-order traversal of a binary tree.

Upvotes: 1

jogojapan
jogojapan

Reputation: 69977

Yes, that can be a problem. It is not a problem right now because you never use the return value, except in the first call (when the function returns the newly created root node).

In all later calls to insert the return value is undefined. If the caller uses the undefined pointer it gets from insert, you will see strange and hard-to-debug problems, or segmentation faults.

Define what the function is expected to return (e.g. 'the last node that was created' or 'the node from which the last insert was made' or similar), and then make sure it returns that. If you think there are situations in which there is nothing the function could reasonably return, at least have it return 0 (or nullptr).

It is also a good idea to document what a function can be expected to return in a comment, even if you are the only person who will ever use the function. At some point you will forget what exactly the function does, and then the comment will be useful.

Upvotes: 1

Related Questions