How does this C code reverse the binary tree in situ?

Question

I've been asked by my teachers to write a function in C that mirrors a binary tree, and by that I mean that inverts the tree. I've been struggling with this question because the solution doesn't make any sense to me. The data struct we use is the following:

typedef struct nodo {

  int valor;

  struct nodo *esq, *dir;
} *ABin;

and the solution is:

void mirror (ABin *a) {

    ABin c = *a;
   if (c == NULL);

    else {
        ABin e = c -> esq;
        ABin d = c -> dir;
        c -> esq = d;
        c -> dir = e;
        mirror (&(c -> esq));
        mirror (&(c -> dir)); 
    }
}

My biggest concern here is the use of pointers or not. I don't understand why, when we call the function recursively, we have to use & when esq and dir are already pointers to the struct nodo type?

You are missing a clear question, methinks. One you could put in the title. — Raphael, Jun 19 '17 at 20:51
The `typedef` is apparently written for maximal confusion. `ABin` is `struct nodo*`, so the `ABin*` parameter is `struct nodo**`. (Please never do this in real code.) — Ry-, Jun 19 '17 at 20:55
Note that the dot `.` and arrow `->` operators bind very tightly indeed and should never be surrounded by spaces. And they bind so tightly that you don't need the parentheses in `&(c->esq)` — `&c->esq` is perfectly sensible and looks less like novice code. — Jonathan Leffler, Jun 19 '17 at 21:41
See [Is it a good idea to typedef pointers?](http://stackoverflow.com/questions/750178/is-it-a-good-idea-to-typedef-pointers) — to which the succinct answer is "No, unless it's a function pointer". — Jonathan Leffler, Jun 19 '17 at 21:47
From the bizarre typedefs and member naming, it looks to me like your teachers were purposely trying to confuse you. — jschultz410, Jun 19 '17 at 22:04

jschultz410 · Answer 1 · 2017-06-20T04:58:03.980

The higher level answer to your question is that by recursively swapping every node's left and right subtrees, you reverse the tree's ordering invariant.

Typically, a binary search tree maintains the invariant that every left descendant orders earlier (or equal to) than the current node, while every right descendant orders later (or equal to) the current node according to the ordering function of the tree. By swapping the left and right subtrees at every node in the tree, you reverse the ordering invariant of the tree.

As to your question about the level of pointer indirection, there is no good reason for the mirror function to take an ABIN pointer. It should just take an ABIN as that is a pointer to a tree node by typedef. Even better, you (or your teachers) wouldn't make a typedef for a pointer to a struct in the first place without good reason.

score 0 · Answer 2 · answered Jun 19 '17 at 20:57

You only need to swap the pointers (even if one of them is NULL)

struct node {
        struct node *prev;
        struct node *next;
        int key;
        char payload[123];
        };

void mirror(struct node *ptr)
{
struct node *tmp;

if (!ptr) return;

tmp = node->prev;
node->prev = node->next;
node->next= tmp;

mirror(node->prev);
mirror(node->next);
}

score 0 · Answer 3 · edited Jun 19 '17 at 21:49

0

As you can see esq and dir are pointers to a struct nodo.

Using the typedef struct nodo{} *ABin makes ABin type also a pointer to a struct nodo.

so

ABin is equivalent to struct nodo * (types).

So, for your function void mirror (ABin *a), a would be a pointer to a pointer.

parameter a  is struct nodo** // pointer to a  pointer

Your function must modify the pointer itself so you must pass its address; that's why you call the function with &.

edited Jun 19 '17 at 21:49

Jonathan Leffler

730,956
141
904
1,278

answered Jun 19 '17 at 21:02

Cioaca Radu

88
8

Alternatively, and more sensibly, use `void mirror(ABin a)` since the code does not modify what `a` points at — there is no `*a = …` assignment. – Jonathan Leffler Jun 19 '17 at 21:50

score 0 · Answer 4 · answered Jun 19 '17 at 21:04

You are making a typedef for a pointer.

 typedef struct nodo* ABin;

This is asking for confusion! In fact, it seemed to have confused you because

void mirror(ABin*)

is the same as

void mirror(struct nodo**)

and there's no reason for that extra layer of indirection. You could change that to

void mirror(ABin)

but it's best to avoid making typedefs for pointers in the first place.

Cleaned up:

typedef struct Nodo {
    int valor;
    struct Nodo* esq;
    struct Nodo* dir;
} Nodo;

void mirror(Nodo* nodo) {
    if (nodo == NULL)
        return;

    Nodo* tmp = nodo->esq;
    nodo->esq = nodo->dir;
    nodo->dir = tmp;

    mirror(nodo->esq);
    mirror(nodo->dir); 
}

How does this C code reverse the binary tree in situ?

4 Answers4