So say we have a cube in 3D that describes a space. We subdivide this cube into 8 different smaller cubes that describe an eighth of the space and we proceed to do this some number of times.
This is a tree, where the root is the full space and each child node is a subsection of a higher subdivision level up to a maximum resolution.
i.e first level is the full space, the next is 8 sub spaces, the next 64 sub spaces... up to 8^n subspaces.
Each one of these nodes can exist in one of two states, occupied or empty. Empty nodes do not have any children, occupied nodes have at least one non empty child unless they are a leaf.
I am given an array of the lowest resolution level (the smallest subspaces, i.e the leafs). This array contains the discretized (x,y,z) coordinates of occupied leafs. In other words, only occupied leafs exist in this array, empty leafs are not explicitly given, so if a leaf is not found in this array we can assume it to be empty.
The information is not given in any particular order, but each leaf self identifies it's position in the 3D space through its (x,y,z) coordinate.
Using this information, we want to construct the described tree. In other words, we want to create a oct-tree where empty leaves have no children.
How could I build the mentioned tree in an efficient manner?
A straightforward way is to insert the leaves one by one in an initially empty octree, and create the missing nodes as you go.
The total cost will be roughly proportional to the number of leaves times the (average) tree height.