# What is the index of the leftest child of node in a k-nery heap?

Suppose the root node‘s index is 1, what is the index of the leftest child of a node e in a k-nery heap? What is the parent‘s index of a node in k-nery heap?

All questions regarding my problem I found talk about binary heaps, I just can’t think of a simple solution.

• The answer depends on the order in which you store the nodes. – Yuval Filmus Jun 21 '19 at 18:43

Let's assume you store the nodes by level and then from left to right. Here are the first few levels:

1. Root: $$1$$
2. Children of root: $$2,\ldots,k+1$$
3. Grandchildren of root: Children of $$2$$: $$k+2,\ldots,2k+1$$; Children of $$3$$: $$2k+2,\ldots,3k+1$$, ...

Let us guess that just like in the binary case, the formula for the leftmost child of $$v$$ is of the form $$\alpha v + \beta$$.

If we consider two adjacent nodes at the same level, their leftmost children will differ by $$k$$ (for example, leftmost child of $$2$$ is $$k+2$$, whereas leftmost child of $$3$$ is $$2k+2$$), hence $$\alpha = k$$.

We can find $$\beta$$ by considering the root: $$k \cdot 1 + \beta = 2$$ implies that $$\beta = -(k-2)$$. Overall, we get $$kv-(k-2) = k(v-1) + 2.$$ This works for the root by construction. When $$v = 2$$, we get $$k (2-1) + 2 = k+2$$, which also works out. My guess it that this formula works out, and you should be able to prove it by induction. That's where you come in...

• Thank you, this worked out for me, also, thanks for the explanation. I did prove it with induction and it seems to work :). – user106782 Jun 24 '19 at 20:47