Parent and childs of a full d-node tree

If you use zero-based indexing, so that the root is position $0$, then the last node in level $ell$ of the tree has index $sum_{i=1}^ell d^i=frac{d(d^ell-1)}{d-1}$. Thus, node $k$ is in level $ell$ iff

$$frac{d}{d-1}(d^{ell-1}-1)<klefrac{d}{d-1}(d^ell-1);,$$

or

$$d^{ell-1}<kleft(1-frac1dright)+1le d^ell;,$$

i.e.,

$$ell=leftlceillog_dleft(kleft(1-frac1dright)+1right)rightrceil;.$$

Let

$$ell(k)=leftlceillog_dleft(kleft(1-frac1dright)+1right)rightrceil;,$$

the level of node $k$. Node $k$ has

$$k-frac{d(d^{ell-1}-1)}{d-1}-1$$

predecessors in level $ell(k)$, each of which has $d$ offspring, so its $d$ offspring have indices from

$$frac{d(d^ell-1)}{d-1}+dleft(k-frac{d(d^{ell-1}-1)}{d-1}-1right)+1=dk+1$$

through $dk+d=d(k+1)$.

Now assume that $k>0$, and node $m$ is the parent of node $k$. Then

$$dm+1le kle d(m+1);,$$

so

$$m+frac1dlefrac{k}dle m+1;,$$

and therefore $$leftlceilfrac{k}drightrceil=m+1;,$$

i.e.,

$$m=leftlceilfrac{k}drightrceil-1;.$$

It looks like you're starting numbering at 1 for the root, and numbering "left to right" on each level/depth.

If the root has depth $0$, then there are $d^{t}$ nodes with depth $t$ from the root in a full $d$-dimensional tree. Also, the depth of node $k$ is $ell_{k}=lceillog_{d}(k-1)rceil$.

The number of nodes at depths below the depth of node $k$, then, is $$n_{k} = sum_{i = 0}^{ell_{k-1}}d^{i} = frac{d^{ell_{k}}-1}{d-1}.$$ So indexing on the row containing node $k$ starts at $n_{k}+1$.

Children of node $k$:

The position of $k$ in its row is just $p_{k}=k-n_{k}$. The children of node $k$ have depth one more than that of $k$, and in their respective row, the first child $c$ has position $d(p_{k}-1)+1=d(k-n_{k}-1)+1$, so the $j^{th}$ child of $k$ has position $$j + sum_{i = 0}^{ell_{k}+1}d^{i} + d(k-sum_{i = 0}^{ell_{k}}d^{i}-1) = j + frac{d^{ell_{k}+1}-1}{d-1} + d(k-frac{d^{ell_{k}}-1}{d-1}-1)$$ $$=j +dk-d +1$$

Parent of node $k$:

Since this formula applies for the parent $p$ of $k$, for $1 leq j leq d$ $$1+dp-d +1leq k leq d+dp - d + 1 = dp+1$$ $$Rightarrow dp - d leq k-1 leq dp$$ $$Rightarrow p-1 leq frac{k-1}{d} leq p$$ so $p = lceilfrac{k-1}{d}rceil$.

Start by labeling your $k$-ary tree with the root as $0$, and continue in a breath-first-search pattern.

1. Given a node $n$, with index $ntext{.i}$, $n$'s children have indices: $${(ntext{.i})k+1,, (ntext{.i})k+1,, ldots,, (ntext{.i})k + k}$$

2. We can also see that given a node $n$ with index $ntext{.i}gt0$, we can find the index of the parent by the formula: $$ptext{.i}=leftlfloorfrac{ntext{.i} - 1}{k}rightrfloor$$

I haven't proved these, but these formulas appear to be correct based on several different drawings.