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

1 Answer 1

To answer your questions:

  1. Indeed, the parent of $n$ is $\lfloor n/2 \rfloor$.
  2. The distance from $n$ to the top is $\lfloor \log_2(n) \rfloor$.
  3. All even numbers are on the left of their parent. If $n \equiv 0,1 \mod 4$ then it is on the left of its second parent. Generally, if $n \mod 2^k \in \{0, 1, \ldots, 2^{k-1} - 1\}$, then it is on the left of it's $k$th parent.

Regarding the references: There are plenty of books about data structures that also cover binary trees. At my university a course on data structures used the book Introduction to Algorithms.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.