Intuitive derivation of formulas for finding the i-th child of a node in a complete tree with a skip

Question

In response to this, I used two formulas that I came to ad-hoc means, and I find it difficult to simply explain why these formulas work. That's the problem:

Consider perfect or fill in a K-ary tree of height H, where each node is marked with its rank in width - the first round, and its dual, where each node is marked in depth-first order. Here is an example with K = 2, H = 2:

_ 0 _ _ 0 _ / \ / \ 1 2 1 4 / \ / \ / \ / \ 3 4 5 6 2 3 5 6 

For a BF-ordered tree, the i-th child of a node N at depth D is defined as follows:

K*N + 1 + i

For a DF-ordered tree, the ith node N child at depth D is defined as follows:

N + 1 + i*step, where step = (K^(H - D) - 1) / (K - 1)

What is an intuitive explanation of these formulas?

The formula ordered by BF makes sense to me when you look at any hand-drawn example, but I cannot say in words why it works. In a DF-ordered case, the best I can come up with is this:

When a node N is at depth D in a K-ary tree with height H having DFS, his first child is just N + 1, because this is the next node to be visited in the first passage in depth, The second child from N will be visited immediately after visiting the entire subtree rooted on the first child element (N + 1), which in itself is a complete K-ary tree of height H - (D + 1) . The size of any complete, K-ary tree is determined by the sum of the finite geometric rows, as described here. The size of the specified subtree is the distance between the first and second children and, in fact, this is the same distance between all brothers and sisters, since each of their subtrees is the same size. If we call this distance step , then:

1st child N + 1 2nd child N + 1 + step 3rd child N + 1 + step + step ... etc.

Can someone give a better explanation of how and why these formulas work?

Answer 1

For BFS:

If node N is at depth D , and before N nodes a are at depth D (and b are nodes after):

 N = K^0 + K^1 + ... + K^(D-1) + a 

How many nodes will be marked before the first child? At the vertices D and a * K "daughter" nodes at a depth of D+1 there are b remaining nodes at depths D and a * K Therefore, if C is the label of the first child of N :

 C = N + b + a * K + 1 C = K^0 + K^1 + ... + K^(D-1) + a + b + a * K + 1 C = K^0 + K^1 + ... + K^(D-1) + K^D + a * K 

Indeed, there are nodes K^D at depth D , therefore a + b + 1 = K^D , for which:

 C = 1 + (K^0 + ... + K^(D-2) + K^(D-1) + a )* K C = 1 + N*k 

For DFS:

To calculate the step size, you must calculate the size of the remaining subtree and, as a subtree of a perfect K-ary tree, is itself an ideal K-ary tree, you can calculate its number of nodes.