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.