Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let us assume my tree starts with $1$ node, then each node has $2$ nodes beneath it. Let us also assume the top node of the tree is numbered $1$, and node $2$ and $3$ are directly beneath it. An entire row of nodes must fill before any new child nodes get added (so $4, 5, 6, 7$ most fill in beneath $2$ and $3$ before $4$ can get any child nodes).

Can anyone help me with formulas that will:

  1. Tell me the parent node number of my current node number (so $7$'s parent node is $3$), I'm pretty sure I just floor(node number/children per parent). Is this correct?
  2. Tell me how many nodes from the top of the tree I am, so distance($8$) = $3$ since it is $3$ generations from the top, without utilizing recursion in my code to traverse the tree and count.
  3. Tell me which side (left/right, assuming $2$ is left and $3$ is right of 1) any node is under any given parent (so side($8,4$) = left, side($13,6$)=right and side($12,1$)=left)

Is there a good resource to go to for more education on problems like this? I work with trees a lot but all of my work is done using expensive recursion when it happens on large structures.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.