CODEWITHSUNDEEP
cpointersbinary-tree
Robbie
Robbie

Reputation: 1774

Why does this pointer arithmetic not work?

In my program, I have a binary tree that is defined as follows:

struct node {
    char value; 
    struct node *left, *right;
};

In my program, I am attempting to write a function that returns a string of each nodes value in index order (top-bottom, right-to-left traversal).

In an attempt to do so, I have written the following function:

char *to_string_util(struct node *root, char *str) {

    if (!root) return str;

    *str++ = root->value;

    // If not NULL
    if (root->left) to_string_util(root->left, str);
    if (root->right) to_string_util(root->right, str);

    return str;
}

This seems like it should work but alas, it does not. I have gotten it to work by using array indexing, which works but is undesirable as it requires the introduction of another variable.

Here is the version that works:

char *to_string_util(struct node *root, char *str, int *cur_pos) {

    if (!root) return str;

    str[(*cur_pos)++] = root->value;

    if (root->left) to_string_util(root->left, str, cur_pos);

    if (root->right) to_string_util(root->right, str, cur_pos);

    return str;
}

Given the tree:

             +
           /   \
          *     *
         / \   / \
         a  a  b  b

The result should be:+*aa*bb

One thing to note is that I call this function in another function which appends a null character to the end of it, which should not affect the output but I thought might be worth mentioning.

Why does the second version using array indexing work but the first does not?

Upvotes: 0

Views: 75

Answers (1)

AnT stands with Russia
AnT stands with Russia

Reputation: 320787

It does not work because you are ignoring the new value of str returned from your recursive sub-calls. Your function is designed to update the value of str and return the new value by doing return str;. And you are just discarding the returned value. For this reason, at each recursive level the call for the right subtree overwrites the data written by the recursive call to the left subtree.

This is probably closer to what you had in mind

// If not NULL
if (root->left) str = to_string_util(root->left, str);
if (root->right) str = to_string_util(root->right, str);

And, of course, you should remember to zero-terminate your string in the end.

If your function begins with 

if (!root) return str;

then the recursive sub-calls don't really need a null check and can be simplified to 

str = to_string_util(root->left, str);
str = to_string_util(root->right, str);

(unless you see it as an optimization).

Your index-based version no longer depends on the updates of str (and does not update it at all). It depends on the updates of position value *cur_pos. Since the position value is passed between different levels of recursion by reference, all levels of recursion see these updates.

You can use the same technique in the first version as well, i.e. pass your pointer value by reference. But for that you'd have to pass str as char **str (a pointer-to-pointer) and use *str and the current character pointer.

Upvotes: 4

Related Questions