struct tree
{
    int elem;
    struct tree *left, *right;
};

int main(int argc, char **argv)
{
    printf("sizeof(int)=%d,sizeof(struct tree)=%d\n",
            sizeof(int),sizeof(struct tree));
}
[download]

I said "generic" tree, along the lines of a glib GTree. So, there's an extra pointer to the data:

struct Node
{
  gpointer data;
  struct Node *left;
  struct Node *right;
}
[download]

So, 3 (probably 4 byte) pointers, plus the data pointed to.

The perl implementation, though, is not a simple struct. Instead, the three members are SVs in an array, and an SV is significantly larger than a single pointer. Then there's some additional overhead for book-keeping on the array.

If anyone out there is in the know, I'd still be interested how you get from the ~76 byte guesstimate, to the 112 byte answer. There must be some low-level document somewhere where it is explained (or maybe a pointer to a chunk of code). I'm still looking at PerlGuts Illustrated. And I think we can all agree that a less bloated way to represent trees in Perl6 would be nice. Right?