Binary Tree implementation C++

Question

Binary Tree insertion:

#include "stdafx.h"
#include <iostream>

using namespace std;

struct TreeNode {
  int value;
  TreeNode* left;
  TreeNode* right;
};

struct TreeType {
  TreeNode* root;

  void insert(TreeNode* tree, int item);

  void insertItem(int value) {
    insert(root, value);
  }
};

void TreeType::insert(TreeNode* tree, int number) {
  if (tree == NULL) {
    tree = new TreeNode;
    tree->left = NULL;
    tree->right = NULL;
    tree->value = number;
    cout << "DONE";
  } else if (number < tree->value) {
    insert(tree->left, number);
  } else {
    insert(tree->right, number);
  }
}

int main() {
  TreeType* MyTree = new TreeType;
  MyTree->insertItem(8);

  return 0;
}

I am currently learning Data structures in C++ and this is the code that make insertion in binary trees.

After it is compiled, everything looks fine, however when i try to execute this program, it crashed.

Can anybody tell me where I am wrong?

Answer 1

In your tree constructor, you need to initialize the root pointer to NULL. It's not guaranteed to be initialized as NULL.

When you compile in linux, you can use gdb to show where the source of the segfault is coming from.

Some other notes:

1. You should assign the value back to root after you've allocated the new node. You're not doing that because you're missing one of the fundamentals of c++. That is, it's based on c. And the thing about c is that is strictly a "by-value" function/method calling paradigm. So all parameters in a function call are by value. When you pass in the memory address for root, you're actually copying the value of the pointer. Then, you're only updating the local value. You need to assign it back to root. If you'd like to learn that concept front to back, I highly recommend watching Jerry Cain's Programming Paradigms course at Stanford.
2. In your main function, you should try to keep the symbol names as lower_case instead of CamelCase. This helps differentiate variables from types (types should stay CamelCase).
3. In your TreeType::insert method, you should call the variable tree_node instead of tree. Doing so helps reflect the correct type and avoids confusion.
4. Whenever possible, try you use the this->root and this->insert notation. Not only will it correctly resolve if you accidentally create a locally scoped root variable, but it's also clearer to the reader where the data or method is defined. Great coding is about communication. It may only take 100-500ms less for the reader to understand where the symbol points to; however, the tiny savings that you can accumulate in avoiding ambiguities add up into a much clearer piece of software. Your future self (and your colleagues) will thank you. See http://msmvps.com/blogs/jon_skeet/archive/2013/09/21/career-and-skills-advice.aspx

Lastly, I can't overstate enough how important learning from the source is. If you're learning c or c++ for the first time, read http://www.amazon.com/The-Programming-Language-4th-Edition/dp/0321563840 and http://www.amazon.com/Programming-Language-2nd-Brian-Kernighan/dp/0131103628. It will save you hours, upon hours, upon hours. After having learned from the source, programming is also A LOT more enjoyable because you understand a good portion of the concepts. And, the truth is, things are more fun when you have a decent level of competence in them.