Path-Indexed Prefix Tree

Classifying numbers with respect to their path

We will now consider yet another binary tree, called Path-Indexed Prefix Tree (PIPTree).

PIPTree(4) top: prefix, mid: number, bottom: path (index)

A PIPTree for a natural number $k$ is defined as follows:

• Nodes are indexed, with the root index as 1.

• For a node with index $i$, the left child has index $2i$ and right child has index $2i + 1$.

• Each node represents the following:

  • A path $p$ that is the binary representation of node index $i$. The length of path is $k$.

  • A number $n$ at path $p$, that is $n = P^{-1}(p)$.

  • A prefix $\rho$ defined by the ECFs of sequences of $n$ and the next number at that path, calculated as $P^{-1}(p) + 2^{|p|}$.

In a PIPTree for paths of length $k$, there will be $2^k-1$ nodes.

Notice that path with all zeros is not considered here, which would be a problem as we have previously mentioned powers of two have path of all zeros. Instead, we append 1 to their path, assigning them to the root.

Numbers

Due to path indexing and the nature of $P^{-1}(p)$, we get the following property: for a node with number $n$:

• the left child has number $n/2+r$ where the root number is $r$
• right child has number $n/2$

It is quite a neat property that this way, you will obtain all numbers from $1$ to $2^{k}-1$. Furthermore, the leaf nodes will all be odd numbers, and the rightmost branch of the tree will all be powers of two.

Prefixes

When we examine the prefix of each node, we notice a pattern. Consider a node with prefix $\{p_0, p_1, \ldots, p_m\}$, and root prefix $\{p_r\}$. There are two observed cases:

🟢 The good case:

• Left child has prefix $\{p_0-1, p_1-1, \ldots, p_m-1, p_r\}$
• Right child has prefix $\{p_0-1, p_1-1, \ldots, p_m-1\}$

🔴 The bad case:

• Left child has prefix $\{p_0-1, p_1-1, \ldots, p_m-1\}$
• Right child has prefix $\{p_0-1, p_1-1, \ldots, p_m-1, p_r\}$

We will refer to this property as the nature of a node, i.e. a node can have good nature or bad nature. The good case is named so because the bijective map of prefix behaves exactly the same as the number does. It is the opposite for the bad case.

As you might guess, this is the source of colors we can see in our tree example. It is really hard to come up with any pattern regarding the nature of a node; nothing seemed evident to the author nevertheless.

Computationally, one can calculate the children and check the prefix to find the nature, but that is not satisfactory. We would like to find the nature of any node, just by looking at that node! There is a way to do so. 🎉

Finding Nature