Binary Tree of Strings returning wrong order

Question

I am fairly new to C and have been learning from K&R's book The C Programming Language. After doing the exercises on Binary trees I wanted to make a header for binary trees for char*, long and double.

There is a function in the following code that has been giving me grief - it should fill an array of character pointers with the values stored in the tree in lexicographical order however it has a bug somewhere. Here's the code for the String Tree Header btree.h:

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

    /************** TYPES **************/
    typedef struct ctree 
    {
        char *name;
        ctree *left;
        ctree *right;
    }; 
    /************** Globals **************/

    static int c_inc = 0;

    /************** Function Prototypes **************/

    ctree *add_to_c_tree  (ctree *cnode, char *name);
    void print_c_tree     (ctree  *cnode);
    ctree *c_tree_alloc   (void);
    void   c_tree_free    (ctree  *cnode);
    void  return_c_tree   (ctree  *cnode, char **array);

    /************** Function Definitions **************/

    /* add_to_c_tree() : Adds a new node to a *character binary tree */
    ctree *add_to_c_tree (ctree *cnode, char *name){

        /* If the node is null, allocate memory for it, 
         * copy the name and set the internal nodes to null*/
        if(cnode == NULL){
            cnode = c_tree_alloc();
            cnode->name = strdup(name); 
            cnode->left = cnode->right = NULL;
        }
        /* If initialised then add to the left node if it is lexographically
        * less that the node above it else add it to the right node */
        else{
            if(strcmp(name, cnode->name) < 0)
                cnode->left  = add_to_c_tree(cnode->left,name);
            else if(strcmp(name, cnode->name) > 0)
                cnode->right = add_to_c_tree(cnode->right,name);

        }

        return cnode;
    }
    /* print_c_tree() : Print out binary tree */
    void print_c_tree(ctree *cnode){
        if (cnode != NULL) { 
            print_c_tree(cnode->left); 
            printf("%s\n",cnode->name); 
            print_c_tree(cnode->right);
        }
    }
    /* return_c_tree() : return array of strings containing all values in binary tree */
    void  return_c_tree   (ctree *cnode, char **array){

        if (cnode != NULL) { 
            return_c_tree (cnode->left,array+c_inc);
            c_tree_free(cnode->left); 
            *(array+c_inc++) = strdup(cnode->name);
            // printf("arr+%d:%s\n", c_inc-1,*(array+(c_inc-1)));
            return_c_tree (cnode->right,array+c_inc); 
            c_tree_free(cnode->right);
        }
    }
    /* c_tree_alloc() : Allocates space for a tree node */
    ctree *c_tree_alloc(void){
        return (ctree *) malloc(sizeof(ctree));
    }
    /* c_tree_free() : Free's Memory */
    void c_tree_free  (ctree *cnode){
        free(cnode);
    }

Which I have been testing with bt.c:

    #include "btree.h"

    int main(void){

        ctree *node = NULL; char *arr[100];

        node = add_to_c_tree(node, "foo");
        node = add_to_c_tree(node, "yoo");
        node = add_to_c_tree(node, "doo");
        node = add_to_c_tree(node, "woo");
        node = add_to_c_tree(node, "aoo");
        node = add_to_c_tree(node, "boo");
        node = add_to_c_tree(node, "coo");

        print_c_tree(node);

        return_c_tree(node,arr);
        for (int i = 0; i < 7; ++i)
        {
            printf("%d:%s  ..\n",i, arr[i]);
        }
        return 0;
    }

The reason for this question is that I have been having issues with the return_c_tree() function, which is meant to mimic the behaviour of K&R's print_c_tree() function except instead of recursively calling itself until a NULL ptr and printing out the name of the nodes in lexicographical order it is meant to add their names to an array of character ptrs and free the nodes memory.

However the output I get when run as above is:

    aoo
    boo
    coo
    doo
    foo
    woo
    yoo
    0:aoo  ..
    1:(null)  ..
    2:boo  ..
    3:doo  ..
    4:foo  ..
    5:coo  ..
    6:(null)  ..

Which shows that the print function works fine but the return function obviously isn't. The confusing thing is that if the call to printf() in return_c_tree() is uncommented this is the result:

    aoo
    boo
    coo
    doo
    foo
    woo
    yoo
    arr+0:aoo
    arr+1:boo
    arr+2:coo
    arr+3:doo
    arr+4:foo
    arr+5:woo
    arr+6:yoo
    0:aoo  ..
    1:(null)  ..
    2:boo  ..
    3:doo  ..
    4:foo  ..
    5:coo  ..
    6:(null)  ..

Which implies that it actually does add the strings in the right order. Also I have tried it without the c_inc variable -> ie just incrementing array before passing it to the right node which the produces the same results from the printf in return_c_tree() but different from main:

    arr+-1:aoo
    arr+-1:boo
    arr+-1:coo
    arr+-1:doo
    arr+-1:foo
    arr+-1:woo
    arr+-1:yoo
    0:foo  ..
    1:yoo  ..
    2:coo  ..
    3:(null)  ..
    4:(null)  ..
    5:(null)  ..
    6:(null)  ..

I'm rather confused, so If anyone can help I would appreciate it greatly. I'm sure I'm just incrementing it in the wrong place but I can't work out where.

I thought I had finally understood pointers but apparently not.

Best P

Answer 1

Your problem is how you handle your pointer to array when you recursively call. This will fix your return_c_tree function:

void  return_c_tree   (ctree *cnode, char **array)
{

  if (cnode != NULL) { 
    return_c_tree (cnode->left,array); // <--- CHANGED 2ND PARAM
    c_tree_free(cnode->left); 
    *(array+c_inc++) = strdup(cnode->name);
    return_c_tree (cnode->right,array); // <--- AGAIN, CHANGED 2ND PARAM
    c_tree_free(cnode->right);
  }
}

You're using a global variable c_inc to keep track of the current index into the array. However, when you recursively called return_c_tree, you passed in array+c_inc, but you did not offset c_inc to account for this. Basically, you double-counted c_inc each time.

While this solves your particular problem, there are some other problems with your code.

1. In general, using global variables is asking for trouble. There's no need to do it here. Pass c_inc as a parameter to return_c_tree.

2. Also, mixing global variables with recursion is especially prone to problems. You really want recursive routines to keep their state on the stack.

3. As a commenter pointed out, all of your code in btree.h should really be in btree.c. The point of header files is to define an interface, not for code.

4. (This is more stylistic) Your return_c_tree function is really two distinct functions: copy the elements of the tree (in order) into the array, and free the memory used by the tree. These two operations are conceptually distinct: there are times that you'll want to do one and not both. There can be compelling performance (or other) reasons to mix the two, but wait until you have some hard evidence.