Binary tree

[Nathalie]

Hello everyone, again trying to help a friend who wrote this code to make a binary tree. It should then show the biggest and smallest number in the tree then delete them and show the last content. Unfortunately this code gives a segmentation error - if anyone could find the problem I would be really grateful. *C only, no C++ please*

#include<stdio.h>
#include<stdlib.h>

typedef struct treeNode
{
   int data;
   struct treeNode *leftNodePtr;
   struct treeNode *rightNodePtr;
}TreeNode;

typedef TreeNode *TreeNodePtr;

void addNode(TreeNodePtr *treePtr, int value);
void writeInceasingOrder(TreeNodePtr treePtr);
TreeNodePtr findSmallest(TreeNodePtr treePtr);
TreeNodePtr deleteSmallest(TreeNodePtr treePtr);

int main(void)
{
   int integer;
   TreeNodePtr rootPtr = NULL;

   printf("Please enter the integer to add tree");
   printf("('-1' to conclude): ");
   scanf("%d",&integer);
   while(integer != -1)
   {
      addNode(&rootPtr, integer);
      printf("add new integer to tree");
      printf("('-1' to conclude): ");
      scanf("%d",&integer);
   }

   writeInceasingOrder(rootPtr);
   printf("\ndeleted: %d", (deleteSmallest(rootPtr)->data));
   writeInceasingOrder(rootPtr);

   return 0;
}

void addNode(TreeNodePtr *treePtr, int value)
{
   if(*treePtr == NULL)
   {
      *treePtr = (TreeNodePtr)malloc(sizeof(TreeNode));

      if(*treePtr != NULL)
      {
	 (*treePtr)->data = value;
	 (*treePtr)->leftNodePtr = NULL;
	 (*treePtr)->rightNodePtr = NULL;
      }
      else
      {
	 printf("not enough memory");
      }
   }
   else
   {
      if(value < (*treePtr)->data)
      {
	 addNode(&((*treePtr)->leftNodePtr), value);
      }
      else
      {
	 if(value > (*treePtr)->data)
	 {
	    addNode(&((*treePtr)->rightNodePtr), value);
	 }
	 else
	 {
	    printf("this number was added earlier");
	 }
      }
   }
}

void writeInceasingOrder(TreeNodePtr treePtr)
{
   if(treePtr != NULL)
   {
      writeInceasingOrder(treePtr->leftNodePtr);
      printf("%3d", treePtr->data);
      writeInceasingOrder(treePtr->rightNodePtr);
   }
}

TreeNodePtr deleteSmallest(TreeNodePtr treePtr)
{
   TreeNodePtr tempPtr;
   if(treePtr->leftNodePtr != NULL && treePtr->rightNodePtr)
   {
      tempPtr = findSmallest(treePtr->rightNodePtr);
      treePtr->data = tempPtr->data;
      treePtr->rightNodePtr = deleteSmallest(treePtr->rightNodePtr);
      return treePtr;
   }
}

TreeNodePtr findSmallest(TreeNodePtr treePtr)
{
   if(treePtr == NULL)
   {
      return NULL;
   }
   else
   {
      if(treePtr->leftNodePtr == NULL)
      {
	 return treePtr;
      }
      else
      {
	 return findSmallest(treePtr->leftNodePtr);
      }
   }
}

[bithub]

The deleteSmallest function doesn't check if treePtr is NULL before dereferencing it.

[Nathalie]

Thanks, hopefully changing that will fix it.

[foxman]

The problem lies in the deleteSmallest function. It doesn't look really good.

So, let's say you want a function who returns the node with the smallest value of a tree and remove that node from that tree (without freeing the memory associated with it). One way to achieve this would be

1. Find the node with the smallest value of the whole tree. Store the adress of that node somewhere.
2. Remove the node from the tree. Since the "smallest node" doesn't have a left child, all you need to do is "parent(smallestNode)->left = smallestNode->right" (in the case smallestNode == root, you'll have a problem of removing the node from the tree since you won't be able to update the root for the new root (root->right). You'll have to change your function prototype if you wan't to resolve this issue).

Note that if you want to use this solution, you'll have to implement a "parent" function, who returns a pointer to the parent of a node.

Also, you could also find a recursive solution. But again, i would highly recommend changing your function prototype before, maybe for something like this

TreeNodePtr deleteSmallest(TreeNodePtr treePtr, TreeNodePtr *smallestNode);
// Should return the root of the tree after removing the smallest node from it.

// Example on how to call the function:
TreeNodePtr smallestNode;
// ...
rootPtr = deleteSmallest(rootPtr, &smallestNode);

or

TreeNodePtr deleteSmallest(TreeNodePtr *treePtr);
// Should return the smallest node of the tree

// Example on how to call the function:
TreeNodePtr smallestNode;
// ...
smallestNode = deleteSmallest(&rootPtr);

If you choose the 2nd solution, you should also choose a non-recursive solution, it will be more straightforward to implement. And if you would like to see some code, i guess i could throw you some.