# Determining number of parent node on an n-tree.

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.

-
yeah (i-1)/n, lemme fix that – CBredlow Dec 20 '13 at 19:28

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)$$
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.