<p>I've been able to test the new method as mentioned in the comments, and it worked perfectly fine.</p>

<p><a href="https://arxiv.org/ftp/arxiv/papers/1505/1505.03090.pdf" rel="nofollow noreferrer">The algorithm that was linked above</a>, implicitly states that the point shall be individually dropped down into the partition tree, passing all the random tests and creating new nodes as it is dropped down.</p>

<hr>

<p>But there is a significant problem with this method, since in order to have a balanced efficient and shallow tree, left and right nodes must be distributed evenly. </p>

<p>Hence, in order to split the node, at every level of the tree, every point of the node must be passed to either left or right node (by a random test), until the tree reaches the depth where all nodes at that level are leaf.</p>

<hr>

<p>In mathematical terms, root node contains a vector space which is divided into two left and right nodes containing convex polyhedrons bounded by supporting hyper-planes by the separating hyper-plane:</p>

<p><a href="https://i.stack.imgur.com/o5tZa.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/o5tZa.gif" alt="enter image description here"></a></p>

<p>Negative term of the equation (I believe we can call it bias), is where the splitting ratio starts to play, it should be percentile of all node points between 100*r to 100*(1-r), so that tree is separated more evenly and it is more shallow. Basically it decides how even should hyper-plane separation be, that's why we require nodes that contain all the points.</p>

<hr>

<p>I have been able to implement such system:</p>

<pre><code>def index_space(self):
    shuffled_space = self.shuffle_space()
    current_tree = PartitionTree()
    level = 0
    root_node = RootNode(shuffled_space, self.capacity, self.split_ratio, self.indices)
    current_tree.root_node = root_node
    current_tree.node_array.append(root_node)
    current_position = root_node.node_position
    node_array = {0: [root_node]}
    while True:
        current_nodes = node_array[level]
        if all([node.is_leaf() for node in current_nodes]):
            break
        else:
            level += 1
            node_array[level] = []
            for current_node in current_nodes:
                if not current_node.is_leaf():
                    left_child = InternalNode(self.capacity, self.split_ratio, self.indices,
                                              self._append(current_position, [-1]), current_node)
                    right_child = InternalNode(self.capacity, self.split_ratio, self.indices,
                                               self._append(current_position, [1]), current_node)
                    for point in current_node.list_points():
                        if current_node.random_test(point) == 1:
                            right_child.add_point(point)
                        else:
                            left_child.add_point(point)
                    node_array[level].extend([left_child, right_child])
</code></pre>

<p>where <code>node_array</code> contains all the nodes of the tree (root, internal and leaf). </p>

<p>Unfortunately, <code>node.random_test(x)</code> method:</p>

<pre><code>def random_test(self, main_point):
    random_coefficients = self.random_coefficients()
    scale_values = [np.inner(self.random_coefficients(), point[:self.indices].ravel())
                                    for point in self.points]
    percentile = np.percentile(scale_values, self.ratio * 100)
    main_term = np.inner(main_point[:self.indices].ravel(), random_coefficients)
    if self.is_leaf():
        return 0  # Next node is the center leaf child
    else:
        if (main_term - percentile) &gt;= 0:  # Hyper-plane equation defined in the document
            return -1  # Next node is the left child
        else:
            return 1  # Next node is the right child
</code></pre>

<p>is inefficient, since calculating percentile takes too much time. Hence I have to find another way to calculate percentile (perhaps by performing short-circuited binary search to optimize percentile). </p>

<hr>

<h1>Conclusion:</h1>

<p>This is just a large extension of Clinton Ray Mulligan's answer - which briefly explains the solution to create such trees and hence will remain as an accepted answer. </p>

<p>I have just added more details in case anyone is interested in implementing randomized binary partition trees.</p>
Are binary partition trees premade before points are added to nodes?
<p>I'm trying to implement <a href="https://arxiv.org/ftp/arxiv/papers/1505/1505.03090.pdf" rel="nofollow noreferrer">this algorithm</a> in Python, but due to my lack of understanding tree structures I'm confused about creation process of the partition tree.</p>

<p><strong>Brief Explanation</strong>:</p>

<p>Algorithm that was linked, is for partitioning a high-dimensional feature space into internal and leaf nodes so that query can be performed quickly. </p>

<p>It divides a large space using specific random test, hyperplane that splits one large cell into two.</p>

<p><a href="https://math.stackexchange.com/a/3044426/513294">This answer explains everything much more precisely</a>.</p>

<p><a href="https://i.stack.imgur.com/Ijl26.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Ijl26.png" alt="enter image description here"></a> </p>

<p>(taken from the link above)</p>

<p><strong>Code Fragments</strong>:</p>

<pre><code>def random_test(self, main_point):  # Main point is np.ndarray instance
    dimension = main_point.ravel().size
    random_coefficients = self.random_coefficients(dimension)
    scale_values = np.array(sorted([np.inner(random_coefficients, point.ravel())
                                    for point in self.points]))
    percentile = random.choice([np.percentile(scale_values, 100 * self.ratio),  # Just as described on Section 3.1
                                np.percentile(scale_values, 100 * (1 - self.ratio))])
    main_term = np.inner(main_point.ravel(), random_coefficients)
    if self.is_leaf():
        return 0  # Next node is the center leaf child
    else:
        if (main_term - percentile) &gt;= 0:  # Hyper-plane equation defined in the document
            return -1  # Next node is the left child
        else:
            return 1  # Next node is the right child
</code></pre>

<p><code>self.ratio</code> as mentioned in the algorithm linked above, is determining how balanced and shallow the tree will be, at <code>1/2</code> it is supposed to generate the most balanced and shallow tree.</p>

<p>Then we move onto the iterative part, where the tree keeps dividing the space further and further until it <strong>reaches</strong> the leaf node (notice the keyword <strong>reaches</strong>), the problem is, it will <strong>never truly</strong> reaches the leaf node. </p>

<p>Since, the definition of leaf node in the document linked above is this:</p>

<pre><code>def is_leaf(self):
    return (self.capacity * self.ratio) &lt;= self.cell_count() &lt;= self.capacity
</code></pre>

<p>where <code>self.cell_count()</code> is number of points in the cell, <code>self.capacity</code> is the maximum amount of points that the cell can have and <code>self.ratio</code> is the split ratio.</p>

<p><a href="https://github.com/ShellRox/Lucifitas/blob/master/core/semantic/polyconvex.py" rel="nofollow noreferrer">My full code</a> should basically divide the feature space by creating new nodes at initial iteration until the leaf node is created (but the leaf node is never created). <a href="https://github.com/ShellRox/Lucifitas/blob/master/core/semantic/polyconvex.py/#L230-L256" rel="nofollow noreferrer">See the fragment that contains the division process</a>.</p>

<p><a href="https://i.stack.imgur.com/EiqXo.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/EiqXo.png" alt="enter image description here"></a></p>

<p>(taken from the document linked above)</p>

<h1>tl;dr:</h1>

<p>Are binary partition trees prepared (filled with empty nodes) before we add any points to them? If so, don't we require to define the level (depth) of the tree?</p>

<p><strong>If not</strong>, are binary partition trees created while adding points to them? If so, then how is the first point (from the first iteration) added to the tree?</p>