The most efficient way of finding/storing neighbourhood info during octree creation
I don't know if there is a way while constructing the oct tree.
But here is way after you created the tree, which runs in O(N), where N is the number of Nodes.
For each node there has to be a maximal comparison of 8*6+7 = 55.
This might can be reduced but this might be fast enough.

loops through all nodes breadth-first.
A neighbour of a child is a neighbour child of the parent or a child of a the parents neighbours.

The comparison if two points are neighbours is here distance(node_1,node_2) == SMALLEST.
I don't know how you compare it. Maybe you can insert your code.
You could caluclate for each level the Euclidian distance of the points if you have equally spaced cuboids
and compare them. That would be the fastest way. 

when nothing works, you can just make a list for each of the 8 comparisons, sort them and keep the lowest one.

call function calc_neighbours(root_node) after you created the oct tree

class Node:
    Node **childs // array of size 8 and pointers to the child node pointers
    Node *parent
    Neighbours **neighbours

function calc_neighbours(root_node):
    queue = create_queue()
    queue.add(root_node)
    while (queue.isEmpty() == false)
    {
        parent_node = queue.pop()
        for (int i = 0; i &lt; 8; i++) // for each child_cube
        {
            queue.push(parent_node-&gt;child[i])
            for (int j = 0; j &lt; 8; j++) // for each neighbour child_cube
                 if (i != j &amp;&amp; distance(parent_node-&gt;child[i],parent_node-&gt;child[j]) == SMALLEST)
                    // filter out those who share only vertex/edge
                    parent_node-&gt;child[i]-&gt;neighbours.add(parent_node-&gt;child[j])
        }
        if (parent_node != root_node)
        // root node has no neighbours, loops through all neighbours of the parent's neighbour's child
            for (int n = 0; n &lt; parent_node-&gt;neighbours-&gt;size(); n++)
                for (int i = 0; i &lt; 8; i++) // for each child_cube
                    for (int j = 0; j &lt; 8; j++) // for each neighbour child_cube
                         if (distance(parent_node-&gt;child[i],parent_node-&gt;neighbours[n]-&gt;child[j]) == SMALLEST)
                            parent_node-&gt;child[i]-&gt;neighbours.add(parent_node-&gt;neighbours[n]-&gt;child[j])
    }