title: Binary Tree Insertion Error
body: <p>I looked at several BST Insert articles but none of them were structured the same as mine or encountered the same problem.</p>
  
  <p>My problem is my Binary Tree isn't being built correctly.  It's really strange because I'm copy+pasting most of the code from a previous project where it works fine, the only difference is the data the nodes contain, and the condition for looping through the tree uses strcmp rather than integer comparison.</p>
  
  <p>This is my insert function:</p>
  
  <pre><code>//insert parameter node data into a Binary Tree
  TreeNodePtr insertNode(BinaryTree bst, Record d)
  {
      //if root is null insert into root
      if(bst.root == NULL)
      {
          bst.root = (TreeNodePtr) malloc(sizeof(TreeNode));
          bst.root-&gt;data = d;
          bst.root-&gt;left = NULL;
          bst.root-&gt;right = NULL;
          return bst.root;
      }
  
      //we need to traverse the tree so declare a pointer "curr" to do so
      TreeNodePtr curr = (TreeNodePtr) malloc(sizeof(TreeNode));
      curr = bst.root;
  
      //loop until we find an appropriate empty space or a match (no duplicates)
      while (strcmp(d.lastName, curr-&gt;data.lastName) != 0)
      {
          if (strcmp(d.lastName, curr-&gt;data.lastName) &lt; 0)
          { // if left
              if(curr-&gt;left==NULL) 
              {
                  curr-&gt;left = (TreeNodePtr) malloc(sizeof(TreeNode));
                  curr-&gt;left-&gt;data = d;
                  curr-&gt;left-&gt;left = NULL;
                  curr-&gt;left-&gt;right = NULL;
                  return bst.root;
              }
              curr=curr-&gt;left;
          }
          else if (strcmp(d.lastName, curr-&gt;data.lastName) &gt; 0)
          { // try right
              if(curr-&gt;right==NULL)
              {
                  curr-&gt;right = (TreeNodePtr) malloc(sizeof(TreeNode));
                  curr-&gt;right-&gt;data = d;
                  curr-&gt;right-&gt;left = NULL;
                  curr-&gt;right-&gt;right = NULL;
                  return bst.root;
              }
              curr=curr-&gt;right;
          }
      }
  
      return bst.root;
  }
  </code></pre>
  
  <p>Here is the code in the main function which uses the insert function to build the tree (note that records is a correctly populated array, each index containing one node's data):</p>
  
  <pre><code>//declare BST and build it
  BinaryTree phoneTree;
  phoneTree.root = NULL;
  
  for (int i=0; i &lt; sizeof(records) / sizeof(Record); i++)
  {
      Record tmpRecord;
      tmpRecord.firstName = records[i].firstName;
      tmpRecord.lastName = records[i].lastName;
      tmpRecord.phoneNum = records[i].phoneNum;
      phoneTree.root = insertNode(phoneTree, tmpRecord);
  }
  </code></pre>
  
  <p>And for reference, here are the tree structs:</p>
  
  <pre><code>//phone data record struct
  typedef struct
  {
      char *firstName;
      char *lastName;
      char *phoneNum;
  }Record;
  
  //define the tree node which contains the data
  typedef struct treeNode
  {
      Record data;
      struct treeNode *left,*right;
  }TreeNode,*TreeNodePtr;
  
  //define binary tree struct
  typedef struct
  {
      TreeNodePtr root;
  }BinaryTree;
  </code></pre>
  
  <p>I've been staring at the program that works and comparing it to this program for about 5 hours now and I can't figure out what's going wrong.  I know the tree isn't populated correctly because if i try to print phoneTree.root->right.data or phoneTree.root->left.data attributes, the program crashes.  In the program I'm borrowing the code from, these attributes are printed without error.  The root is still inserted correctly and it's attributes can be printed.</p>
  
  <p>Any insight as to what I'm doing incorrectly is greatly appreciated.</p>