Thread: Creating a Binary Search Tree

Hi,
I want to create and display a binary search tree of integer keys.
But, I have problem with my inorder function.I simply want to display the resulting ordered list after each insertion by calling function tree_inorder.

Code:

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

#define TYPED_ALLOC(type) (type *)malloc(sizeof (type))

typedef struct tree_node_s {
  int                     key;
  struct tree_node_s     *leftp, *rightp;
}tree_node_t;

tree_node_t *tree_insert(tree_node_t *rootp, int new_key);
void tree_inorder(tree_node_t *rootp);

int
main(void)
{
  tree_node_t *bs_treep;   /* binary search tree                 */
  int          data_key;   /* input - keys for tree              */
  int          status;     /* status of input operation          */

  bs_treep = NULL;    /* Initially, tree is empty */
  
  for (status = scanf("%d", &data_key);
       status == 1;
       status = scanf("%d", &data_key)) {
    bs_treep = tree_insert(bs_treep, data_key);
    printf("Tree after insertion of %d:\n", data_key);
    tree_inorder(bs_treep);
  }

  if (status == 0) {
    printf("Invalid data >>%c\n", getchar());
  }
  else {
    printf("Final binary search tree:\n");
    tree_inorder(bs_treep);
  }
  
  return(0);
}

tree_node_t *
tree_insert(tree_node_t *rootp,   /* input/output - root node of 
				     binary search tree    */
	    int         new_key)  /* input - key to insert */
{
  if (rootp == NULL) {            /* Simple Case 1 - Empty tree */
    rootp = TYPED_ALLOC(tree_node_t);
    rootp->key = new_key;
    rootp->leftp = NULL;
    rootp->rightp = NULL;
  }
  else if (new_key == rootp->key) { /* Simple Case 2 */
    /* duplicate key - no insertion                  */
  }
  else if (new_key < rootp->key) { /* Insert in       */
    rootp->leftp = tree_insert(rootp->leftp, new_key); /* left subtree */
  }
  else {
    rootp->rightp = tree_insert(rootp->rightp, new_key);
  }

  return(0);
}
void tree_inorder(tree_node_t *rootp)
{
  if (rootp == NULL)
  return;
  tree_inorder(rootp->leftp);
  printf("%d", rootp->key);
  tree_inorder(rootp->rightp);
}

It's not your inorder that's broken, it's your insert:

Code:

  return(0);

should be:

Code:

  return rootp;

Also, you don't need TYPED_ALLOC. You're actually better off not casting malloc (read this FAQ article).