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

-

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.

-
Sorry, this is assuming indices are 0-based. And for n=4, I picked a few random numbers, like 97, 256, and 1000 to see if it worked. I would've went higher, but I had a hard time drawing the tree to that level. – CBredlow Dec 20 '13 at 19:38
@CBredlow: I would suggest checking all nodes in the first two or three levels of the tree. If it works for all those, there won't be any differences higher up. – Henning Makholm Dec 20 '13 at 19:41