Insert widget into binary search tree

Question

I’m having a hard time adding an element to a binary search tree. The function returns 1 if the element to be inserted is already in the tree and 0 otherwise. The function return works well but when printing the tree the new element does not appear in the new tree. Here is my code :

int adiciona (Abin a, int x)
{

  int n;

  if (a == NULL)
  {
    Abin novi = (Abin)malloc (sizeof (struct sbin));
    novi->valor = x;
    novi->esq = NULL;
    novi->dir = NULL;
    n = 0;
  }
  else
  {
    if (x == a->valor)
    { n = 1; }
    if (x > a->valor)
    { n = adiciona (a->dir , x); }
    if (x < a->valor)
    { n = adiciona (a->esq , x); }

  }

   return n;
}

Is the error in my code ? If it is, what is the right way to solve this function ?

Answer 1

At no point in this code do you add the new created branches to the top branches of the tree. That’s - you call the function adiciona recursively correctly, the function adiciona creates a new single-level tree and inserts the value, but does not insert this new tree into the parent levels.

Since in C it is complicated a function to return more than one value (in this case its "n" and the new branch of the tree) - the best is to create the new branch, when necessary without calling the add function with a "NULL" as root - (why there it has where to add the created branch).

So maybe one of the simplest ways is to sort of rearrange your function like this

Abin cria(void)
{
  return (Abin)malloc (sizeof (struct sbin));
}

int adiciona (Abin a, int x)
{
  int n;

  if (x == a->valor)
    { n = 1; }
  if (x > a->valor)
    { 
      if (!a->dir)
      { 
        a->dir = cria();
        a -> dir -> valor = valor;   
        n = 0;
      }
      else
      { n = adiciona(a->dir, x); }
    }
  if (x < a->valor)
    { 
      if (!a->esq)
      { a -> esq = cria();
        a -> esq -> valor = valor;
        n = 0;
      }
      else
      { n = adiciona (a->esq , x); }
    }
  return n;
}

(exceptionally I have maintained its indentation pattern - but it is none of the preferred forms for key languages)

Answer 2

You need to do a point to your element novi. It doesn’t print anything because you allocate a value in memory but doesn’t add it to your tree.