Segmentation Fault with BST

[Rodr1697]

I am a bit of a beginner with c++ but I was practicing with binary search trees and for some reason came across a segmentation fault when adding keys to the tree. I was able to figure out that my program seems to iterate through the for loop 7 times in my main.cpp file before coming across the segmentation fault but I can't seem to figure out why. Any help would be greatly appreciated.

/*main.cpp*/
#include <iostream>
#include <cstdlib>

#include "BST.cpp"

using namespace std;

int main()
{

  int TreeKeys[16] = {50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3, 70, 87, 80};
  BST myTree;

  cout << "Printing in order before adding numbers" << endl;

  myTree.PrintInOrder();

  cout << "Printing in order after adding numbers" << endl;

  for(int i = 0; i < 16; i++)
    {
      myTree.AddLeaf(TreeKeys[i]);
    }

  myTree.PrintInOrder();

  cout << endl;

  return 0;
}

/*BST.cpp*/
#include <iostream>
#include <cstdlib>

#include "BST.h"

using namespace std;

BST::BST()
{
  root = NULL;
}

BST::node* BST::CreateLeaf(int key)
{
  node* n = new node;
  n->key = key;
  n->left = NULL;
  n->right = NULL;

  return n;
}
void BST::AddLeaf(int key)
{
  AddLeafPrivate(key, root);
}

void BST::AddLeafPrivate(int key, node* Ptr)
{
  if(root == NULL)     // Empty tree
    {
      root = CreateLeaf(key);
    }

  else if(key < Ptr->key)     //adding to left side
    {
      if(Ptr->left != NULL)
        {
          AddLeafPrivate(key, Ptr->left);
        }
      else
        {
          Ptr->left = CreateLeaf(key);
        }
    }

  else if(key > Ptr->key)     // adding to right side
    {
      if(Ptr->right != NULL)
        {
          AddLeafPrivate(key, Ptr->left);
        }
      else
        {
          Ptr->right = CreateLeaf(key);
        }
    }
}
void BST::PrintInOrder()
{
  PrintInOrderPrivate(root);
}

void BST::PrintInOrderPrivate(node* Ptr)
{
  if(root != NULL)
    {
      if(Ptr->left != NULL)
        {
          PrintInOrderPrivate(Ptr->left);
        }
      cout << Ptr->key << " ";
      if(Ptr->right != NULL)
        {
          PrintInOrderPrivate(Ptr->right);
        }
    }
  else
    {
      cout << "The tree is empty." << endl;
    }
}

/*BST.h*/
class BST
{
 private:

  struct node
  {
    int key;
    node* left;
    node* right;
  };

  node* root;
  node* CreateLeaf(int key);

  void AddLeafPrivate(int key, node* Ptr);
  void PrintInOrderPrivate(node* Ptr);
 public:

  BST();
  void AddLeaf(int key);
  void PrintInOrder();
};

[ne555]

$ gdb a.out
(gdb) run
foo.cpp:90:22: runtime error: member access within null pointer of type 'struct node'

Program received signal SIGSEGV, Segmentation fault.
0x0000555555555c4a in BST::AddLeafPrivate (this=0x7fffffffe0a8, key=15, Ptr=0x0) at foo.cpp:90
90        else if(key < Ptr->key)     //adding to left side
(gdb) backtrace
#0  0x0000555555555c4a in BST::AddLeafPrivate (this=0x7fffffffe0a8, key=15, Ptr=0x0) at foo.cpp:90
#1  0x0000555555555e23 in BST::AddLeafPrivate (this=0x7fffffffe0a8, key=15, Ptr=0x55555576b2e0) at foo.cpp:106
#2  0x0000555555555cea in BST::AddLeafPrivate (this=0x7fffffffe0a8, key=15, Ptr=0x55555576b2c0) at foo.cpp:94
#3  0x0000555555555cea in BST::AddLeafPrivate (this=0x7fffffffe0a8, key=15, Ptr=0x55555576b280) at foo.cpp:94
#4  0x0000555555555b6f in BST::AddLeaf (this=0x7fffffffe0a8, key=15) at foo.cpp:80
#5  0x00005555555558e7 in main () at foo.cpp:47
(gdb) up
#1  0x0000555555555e23 in BST::AddLeafPrivate (this=0x7fffffffe0a8, key=15, Ptr=0x55555576b2e0) at foo.cpp:106
106               AddLeafPrivate(key, Ptr->left);
(gdb) list
101
102       else if(key > Ptr->key)     // adding to right side
103         {
104           if(Ptr->right != NULL) // **right**
105             {
106               AddLeafPrivate(key, Ptr->left); // **left**
107             }
108           else
109             {
110               Ptr->right = CreateLeaf(key);

a copy-paste error, you check the right leaf but go to the left


Apart #include "BST.cpp"
Don't #include source files, you should add them to your project. Each source is compiled separately and then they are all linked together.
Otherwise you are compiling everything every time and also expose yourself to circular references and multiple definitions.
http://www.cplusplus.com/forum/general/140198/
http://www.cplusplus.com/forum/general/113904/


PS: the line numbers don't match yours, put it everything in one file to avoid having to copy your file structure. would appreciate that you do that when posting, or post a link to github or similar to download your entire project.

[Rodr1697]

Ah ha! thank you so much, I honestly don't think I would have ever caught that on my own. And in regard to including source files, that is noted. I usually don't include source files myself either, but I was following a tutorial online. Regardless, I really appreciate it.