Creating binary tree and function overload and convert errors

Question

I am trying to create a binary tree from in order and post order lists. I have two structures, Tree and TreeNode. I call Tree and then TreeNode. I keep getting overload and cannot convert TreeNode to Tree errors. I can't figure out how to add a node with my function.

Can't return the proper structure back from addnode function.

C program to create a binary tree. Need to follow the given structures. Need to call Tree structure first and than TreeNode. The add node function does not work because I can add the node and load the value. Keep getting function overload and cant convert Tree to TreeNode structures errors.

#include "pch.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    int data;
    struct node * left;
    struct node * right;
} TreeNode;

typedef struct trnode
{
    TreeNode * root;
} Tree;

//Prototypes for functions.
Tree * buildTree(int * in, int * post, int size);
TreeNode * addNode(int data);
int search(int inArray[], int strt, int end, int value);
Tree * buildUtil(int inArray[], int postArray[], int inStart, int inEnd, int* pIndex);

Tree * buildUtil(int inArray[], int postArray[], int inStart, int inEnd, int* pIndex)
{
    int indexvalue;
    TreeNode ln;

    // Base case only one node
    if (inStart > inEnd)
        return NULL;

    /* Pick current node from Postorder traversal using
    postIndex and decrement postIndex */

    TreeNode * node = addNode(postArray[*pIndex]);

    (*pIndex)--;

    indexvalue = *pIndex;
    //If this node has no children then return 
    if (inStart == inEnd)

    **//error cannot convert from TreeNode to Tree**
    return node;

    // Else find the index of this node in Inorder traversal
    int iIndex = search(inArray, inStart, inEnd, indexvalue);

   // Using index in Inorder traversal, construct left and right

   //ERROR CANNOT CONVERT from TREE to node
   node-> right = buildUtil(inArray, postArray, iIndex + 1, inEnd, pIndex);
   node ->left = buildUtil(inArray, postArray, inStart, iIndex - 1, pIndex);

   //ERROR CANT CONVERT FROM TREENODE TO TREE
   return node;
}
  // buildtree functioni calls helper function buildUtil which is recursive
Tree * buildTree(int * inArray, int * postArray, int size)
{
    Tree *tr;
    int preindex = size - 1;
    tr->root;
    return buildUtil(inArray, postArray, 0, preindex, &preindex);
}

/* Function to find index of value in arr[start...end]
The function assume List items that value is postsent in in[] */

int search(int inArray[], int strt, int end, int value)
{
    int i;
    for (i = strt; i <= end; i++) {
    if (inArray[i] == value)
    break;
}
   return i;
}
TreeNode addNode(int data)
{
   TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));

   node-> data = data;
   node->left = NULL;
   node->right = NULL;

   // no suitable constructor exists to convert from TreeNode to node
   return (node);
}

int main()
{

// values of in and post lists. I can successfully read both arrays in from my read function
// in { 4, 8, 2, 5, 1, 6, 3, 7 };
// post { 8, 4, 5, 2, 6, 7, 3, 1 };

    int *in = NULL;
    int *post = NULL;
    int insize;
    int postsize;

    insize = 8;
    postsize = 8;

    Tree * tr = buildTree(in, post, insize);
    }

Answer 1

The question code seems to be mixing up a "tree" with a "tree node". Specifically, there will only be one tree, starting with the tree's root node. Child nodes (left and/or right) are attached to the tree's root node. Then grandchild nodes (left-left, left-right, right-left, right-right) recursively until the data is exhausted.

Consider this code, based on the question code (error handling included):

/*------------------------------------------------------------------------
** Compiler setup.
*/
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*------------------------------------------------------------------------
** Memory structures.
*/
typedef struct node
  {
  int    data;
  struct node *left;
  struct node *right;
  } TreeNode_t;

typedef struct Tree_s
  {
  TreeNode_t *root;
  } Tree_t;

/*------------------------------------------------------------------------
** Function to find index of value in arr[start...end]
** The function assume List items that value is postsent in in[]
**
** Returns: EXIT_SUCCESS (0)  Success
**          ENOENT            Search found no matching value.
*/
int Search(int *_O_index, int inArray[], int strt, int end, int value)
  {
  int rCode = EXIT_SUCCESS;
  int index;

  for(index = strt; index <= end; index++)
    {
    if(inArray[index] == value)
      break;
    }

  if(index > end)
    {
    rCode=ENOENT;
    fprintf(stderr, "NOTE: (index[%d] > end[%d])\n", index, end);
    goto CLEANUP;
    }

//RESULTS:
  if(_O_index)
    *_O_index = index;

CLEANUP:

    return(rCode);
  }

/*------------------------------------------------------------------------
** Returns: EXIT_SUCCESS (0)  Success
**          ENOMEM            No memory available.
*/
int AddNode(TreeNode_t **_O_node, int data)
  {
  int rCode = EXIT_SUCCESS;
  TreeNode_t *node = NULL;

  node=malloc(sizeof(TreeNode_t));
  if(!node)
    {
    rCode=errno;
    fprintf(stderr, "ERROR: node=malloc() failed. errno: %d \"%s\" \n", errno, strerror(errno));
    goto CLEANUP;
    }

  node->data = data;
  node->left = NULL;
  node->right = NULL;

//RESULTS:
  if(_O_node)
    {
    *_O_node = node;
    node = NULL;
    }

CLEANUP:

  if(node)
    free(node);

  return(rCode);
  }

/*------------------------------------------------------------------------
** Returns: EXIT_SUCCESS (0)    Success
**          Other errno values  Returned by AddNode(), Search(), BuildUtil().
*/
int BuildUtil(TreeNode_t **_O_node, int inArray[], int postArray[], int inStart, int inEnd, int* pIndex)
  {
  int         rCode = EXIT_SUCCESS;
  TreeNode_t *node  = NULL;
  int         indexvalue;
  int         iIndex;

  /* Base case only one node */
  if(inStart > inEnd)
    {
    fprintf(stderr, "NOTE: (inStart[%d] > inEnd[%d])\n", inStart, inEnd);
    goto RESULTS;
    }

  /* Pick current node from Postorder traversal using
  postIndex and decrement postIndex */
  rCode = AddNode(&node, postArray[*pIndex]);
  if(rCode)
    {
    fprintf(stderr, "ERROR: AddNode() failed. errno: %d \"%s\" \n", rCode, strerror(rCode));
    goto CLEANUP;
    }

  (*pIndex)--;

  indexvalue = *pIndex;
  //If this node has no children then return
  if(inStart == inEnd)
    {
    fprintf(stderr, "NOTE: no children.\n");
    goto CLEANUP;
    }

  // Else find the index of this node in Inorder traversal
  rCode=Search(&iIndex, inArray, inStart, inEnd, indexvalue);
  switch(rCode)
    {
    case EXIT_SUCCESS:
      break;

    case ENOENT:
      rCode = EXIT_SUCCESS;
      goto RESULTS;

    default:
      fprintf(stderr, "ERROR: Search(&iIndex,inArray[%p], inStart[%d], inEnd[%d], indexvalue[%d]) failed. errno: %d \"%s\" \n", inArray, inStart, inEnd, indexvalue, rCode, strerror(rCode));
      goto CLEANUP;
    }

  // Using index in Inorder traversal, construct left and right
  rCode = BuildUtil(&node->right, inArray, postArray, iIndex + 1, inEnd, pIndex);
  if(rCode)
    {
    fprintf(stderr, "ERROR: BuildUtil(node->right, inArray[%p], postArray[%p], iIndex + 1[%d], inEnd[%d], pIndex[%d]) Failed. errno: %d \"%s\"\n", inArray, postArray, iIndex + 1, inEnd, *pIndex, rCode, strerror(rCode));
    goto CLEANUP;
    }

  rCode = BuildUtil(&node->left, inArray, postArray, inStart, iIndex - 1, pIndex);
  if(rCode)
    {
    fprintf(stderr, "ERROR: BuildUtil(&node->left, inArray[%p], postArray[%p], iIndex + 1[%d], inEnd[%d], pIndex[%d]) Failed. errno: %d \"%s\"\n", inArray, postArray, iIndex + 1, inEnd, *pIndex, rCode, strerror(rCode));
    goto CLEANUP;
    }

RESULTS:
  if(_O_node)
    *_O_node = node;

CLEANUP:

  return(rCode);
  }

/*------------------------------------------------------------------------
** BuildTree function calls helper function buildUtil which is recursive
**
** Returns: EXIT_SUCCESS (0)    Success
**          ENOMEM              No memory available.
**          Other errno values  Returned by BuildUtil().
*/
int BuildTree(Tree_t **_O_tree, int *inArray, int *postArray, int size)
  {
  int     rCode    = EXIT_SUCCESS;
  Tree_t *tree     = NULL;
  int     preindex = size - 1;

  tree=malloc(sizeof(Tree_t));
  if(!tree)
    {
    rCode=errno;
    fprintf(stderr, "ERROR: tree=malloc() failed. errno: %d \"%s\"\n", errno, strerror(errno));
    goto CLEANUP;
    }

  rCode = BuildUtil(&tree->root, inArray, postArray, 0, preindex, &preindex);
  if(rCode)
    {
    fprintf(stderr, "ERROR: tree->root = buildUtil() failed. errno: %d \"%s\"\n", rCode, strerror(rCode));
    goto CLEANUP;
    }

//RESULTS:
  if(_O_tree)
    *_O_tree = tree;

CLEANUP:

  return(rCode);
  }

/*------------------------------------------------------------------------
** Program start.
*/
int main()
  {
  int     rCode    = EXIT_SUCCESS;
  int     in[]     = { 4, 8, 2, 5, 1, 6, 3, 7 };
  int     post[]   = { 8, 4, 5, 2, 6, 7, 3, 1 };
  int     insize   = 8;
  Tree_t *tree     = NULL;

  rCode = BuildTree(&tree, in, post, insize);
  if(rCode)
    {
    fprintf(stderr, "ERROR: BuildTree() failed. errno: %d \"%s\"\n", rCode, strerror(rCode));
    goto CLEANUP;
    }

CLEANUP:

  return(rCode);
  }