C++ Branching recursive struct?

Question

I have the following. The struct is prototyped so it compiles fine.

struct vertexNodeInfo
{
    vector<vertexNodeInfo> node;
};

I'm trying to write an octree thingy. What I want to do is use a recursive function to continue adding a node to each node until I get down to a specific point, at which time the function, rather than adding another node, adds a leaf. I want to use no memory when there's no further node or leaf added if that's possible.

Maybe templates would help in this situation, but I'm not sure how to use them...

I don't think I've explained myself well. Here's a diagram:

I have no idea if what I'm asking for is impossible or too confusing to understand or just plain dumb, but I can't figure it out on my own. I'm sorry that I can't explain it any better.

I'm using C++98/03 (VC++2008) and cannot use C++11

Any help at all would be much appreciated.

ADDITIONAL INFO:

Better explanation: I want an array of an array of an array of an array of data. Memory usage is very important in this (I'm storing several million elements, so a single byte makes a huge difference). Each array can contain 8 more arrays, but until I need to use it I want each one of the arrays to use no memory. It's an octree of sorts.

MORE ADDITIONAL INFO:

Here's another diagram. It's a little big, so you might need to right click it and select Open image in new tab to make it readable.

What I don't want are "brown" (red+green) boxes, where every box reserves memory for both more nodes and for the leaf data. That would use far too much memory for my needs.

This is basically what I'm trying to achieve, pictured as 2D for simplicity:

Answer 1

Without any (manual) heap allocation^[1]:

struct NodeInfo { 
    int id; 
};

using Tree = boost::make_recursive_variant<
        NodeInfo,
        std::vector<boost::recursive_variant_>
    >::type;

I know variants come with their own "complexity", but memory locality is preserved and manual memory management avoided.

Now to get closer to your stated optimization goals, you could use std::array<T, 8> instead of the std::vector, or perhaps just make the vector use a custom allocator to allocate from a memory pool.

Sample program (see it Live on Coliru):

#include <iostream>
#include <boost/variant.hpp>
#include <vector>

struct NodeInfo { 
    int id; 
};

using Tree = boost::make_recursive_variant<
        NodeInfo,
        std::vector<boost::recursive_variant_>
    >::type;

// for nicer code:
using Branch = std::vector<Tree>;
using Leaf   = NodeInfo; 

static std::ostream& operator<<(std::ostream& os, Leaf const& ni) { 
    return os << ni.id; 
}
static std::ostream& operator<<(std::ostream& os, Branch const& b) { 
    os << "{ ";
    for (auto& child: b) os << child << " ";
    return os << "}";  
}

int main()
{
    Branch branch1 { 
        Leaf { 2 }, 
        Leaf { 1 }, 
        Branch { 
            Leaf { 42 }, 
            Leaf { -42 }, 
        }
    };

    Tree tree = Branch { branch1, Leaf { 0 }, branch1 };

    std::cout << tree << "\n";
}

Prints:

{ { 2 1 { 42 -42 } } 0 { 2 1 { 42 -42 } } }

---

^[1] (outside the use of std::vector)