1

I have the following recursive function which is supposed to call itself passing a pointer by reference. How can I dereference tmproot->left and tmproot->right so that I can pass it to tree_input()?

typedef struct node_s {

    int value;
    struct node_s *left;
    struct node_s *right;

} node_t;

node_t new_node() {
    node_t *new_node = (node_t*)malloc(sizeof(node_t));
    new_node->left = NULL;
    new_node->right = NULL;
    return *new_node;
}

void tree_input(int value, node_t **tmproot)
{
    if (*tmproot == nullptr) {
        node_t *node = &new_node();
        node->value = value;
    }
    else if (value < (*tmproot)->value) {
        tree_input(value, tmproot->left);
    }
    else if (value >= value) {
        tree_input(value, tmproot->right);
    }
    return;
}

tree_input() is called the first time using tree_input(new_value, &root); I am sure I am missing a simple trick.

j.Doe
  • 202
  • 4
  • 18
  • 1
    @Frank Pure C code compiles in C++ – nicomp May 12 '19 at 21:14
  • 1
    @nicomp The C++ answer involves: "For the love of god, do not use `malloc()` for this", the C answer is different altogether, so the distinction is important, and I thought this was more likely to be a misstagged question than the alternative. –  May 12 '19 at 21:15
  • 2
    @nicomp No, lots of things in pure C code will not compile as C++. There is still a "common subset" that can be used to write code that is valid and has practically the same meaning in both languages, but that excludes many C features. – aschepler May 12 '19 at 21:19
  • To elaborate further on what @aschepler says, the line `(node_t*)malloc(sizeof(node_t));` above is undefined behavior in C++ as it causes a strict aliasing violation (unless it is followed by an in-place new). –  May 12 '19 at 21:27
  • Don't cast the return value of malloc: https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc – alx - recommends codidact May 12 '19 at 21:29

1 Answers1

3

To answer the question as asked:

void tree_input() takes a pointer to a pointer as an argument, and node_s->left is a pointer. So all you have to do is get a pointer to the pointer by using the address-of operand.

However, since tmproot is a pointer-to-pointer, it also needs to be dereferenced once before you can use the -> operator.

tree_input(value, &(*tmproot)->left);

However, you should also know that your new_node() function, and how you use it, is pretty broken.

The way it's setup now, you create a new node_t on the heap, copy it on the stack, and store a pointer to that stack instance in your tree, which immediately becomes a dangling pointer, while the heap-allocated memory just leaks away.

To fix it, the function should return a node_t*, not a node_t. Everything else should flow naturaly from there.

  • 1
    And remove `nullptr`, which is a c++11 feature. `NULL` will do. – Heath Raftery May 12 '19 at 21:30
  • I am getting the following error when using the address-of operand: `main.cpp:64:29: error: member reference base type 'node_t *' (aka 'node_s *') is not a structure or union tree_input(value, &tmproot->left);` as in your example – j.Doe May 12 '19 at 21:34
  • 1
    @j.Doe Sorry about that, I forgot `tmproot` was a double pointer in the first place, so it needs to be dereferenced once before using the `->` operator. I fixed the code. –  May 12 '19 at 21:37
  • Thanks a lot! The code compiles without errors now. However, the only reason why I am using a double pointer is that I want to change `root` not only temporarily because I want to use it in another function. Right now I seem to still be editing that copy `tmproot` of the passed pointer `root`. What's the approach to fix this and do it via reference? – j.Doe May 12 '19 at 21:41
  • 1
    @j.Doe That's what your function does. Of course, `new_node()` being broken the way it is could cause the program to look like it's behaving this way... –  May 12 '19 at 21:45
  • Thanks, I'll have a look at it. – j.Doe May 12 '19 at 21:46