How to efficiently store different node types of an octree

I am struggling my way through implementing a sparse voxel octree, but I don't know how to differenciate between branch and leaf nodes effectively.

One way I thought of was to downcast the Node pointers to a child class, but I fear a big performance hit from casting thousand of times

struct Node
{
    Node* parent;
};

struct Branch : public Node
{
    Node* children[8];
    unsigned char activeChildren = 0;
};

struct Leaf : public Node
{
    unsigned char color[3];
}

Then I read about type unions, but my compiler went wild and I got tons of weird errors when trying to access the unions variables.

struct Leaf
{
    unsigned char r = 0;
    unsigned char g = 0;
    unsigned char b = 0;
};

struct Branch
{
    Node* children[8];
    unsigned char activeChildren = 0;
};

union NodeData
{
    Leaf leaf;
    Branch branch;
};

struct Node
{
    Node* parent;
    NodeData data;
};

Now I'm thinking about storing the data in a bitmask big enough to fit the biggest node type, and setting an extra bit to know if it's a branch or leaf.

class Node
{
public:
    // getter and setter for the nodes content

public:
    Node* parent;

private:
    // bitmask
    // 8*64 bits for pointers to children
    // 8 bit to identify active nodes
    // 
    // 1 bit to identify node type
    // 7 unused bits -> maybe for depth of the node
    unsigned char bitmask[66];
};

How would this be handled usually?

Thanks in advance for your help!

Your options are:

1. Inheritance

Like your original solution. Easy to understand.

template<typename T>
class Node {
};

template<typename T>
class Internal<T> : public Node<T> {
    Node<T> *children[8];
};

template<typename T>
class Leaf<T> : public Node<T> {
    T value;
};

Speed overhead: either one or more virtual functions or dynamic_casting.

Size overhead: one vtable pointer, probably 8 bytes on a 64-bits platform.

2. A discriminated union

Since the two types of nodes occupy the same bytes in memory, you need to add some way to distinguish which of the types is valid.

template<typename T>
class Node {
    bool isLeaf;
    union {
        T value;              // Valid if isLeaf
        Node<T> *children[8]; // Valid if !isLeaf
    };
};

Speed overhead: a boolean check.

Size overhead: one byte, plus probably 7 bytes of padding on a 64-bits platform.

Advanced idea: if sizeof(value) is less than sizeof(children) by at least sizeof(Node<T> *), you can avoid the space overhead of the isLeaf flag by prepending a null pointer to the value. Then you can check if children[0] == nullptr to detect whether it's a leaf. This will usually work, but is technically undefined behaviour.

3. No polymorphism at all

Have a single type that contains both data and pointers to child nodes. You can deduce whether it's a leaf by checking children[0] == nullptr.

template<typename T>
class Node {
    bool isLeaf;
    T value;              // Valid if isLeaf
    Node<T> *children[8]; // Valid if !isLeaf
};

Speed overhead: a pointer check.

Size overhead: either the value or the child pointers are redundant.

So there really is no advantage compared to solution 2.