Determining number of parent node on an n-tree.

Question

I'm sorry if this is the wrong one, was unsure if this was computer science, programming, or mathematics related. I'm going with mathematics because it is semi-graph theory related.

I have a tree with n-child nodes attached to each parent, and I know the indices of each node. Would the appropriate way to determine the parent be

floor((i-1)/n)?

Where i is the index of the new node being added, one to handle the offset of starting at 0 as the root, and n being the number of children allowed per parent.

I know that this holds true for n=2, and from testing it works for n=3, and n=4, but I would like to make absolute certain that it is correct.

Answer 1

Yes, assuming that the tree's root is numbered zero and children are numbered sequentially by levels. Then, the children of node $x$ have numbers $$nx+1, nx+2, nx+3, \ldots, nx+n$$ and, in the other direction, parent of node $x$ has number $$\mathrm{floor}\left(\frac{x-1}{n}\right)$$

Answer 2

Something like that is going to work. Whether subtracting one before dividing is exactly the right thing to do, and which rounding to use, depends on whether your indices are 0-based or 1-based and so forth.

It's probably not worth it to try to figure out the right thing to do from first principles -- just guessing and then verifying that your formula gives the right result for the first few layers for $n=2$ up to $4$ should give you a very high certainty that there aren't any fencepost errors hiding anywhere.