Finding the location of a parent node in a binary tree

Question

So I need help coming up with an expression that will always give me the location of a child's parent node in a binary tree. Here is an example of a problem my teacher will put on our exam:

"Consider a complete binary tree with exactly 10,000 nodes, implemented with an array starting at index 0 . The array is populated in order by extracting elements from the tree one level at a time from left to right. Suppose that a node has its value stored in location 4999. Where is the value stored for this node’s parent?"

My teacher did not tell us how to solve a problem like this. She just said "Draw a binary tree and find a pattern." I did just that but i could not come up with anything! please help. thanks.

Answer 1

The following is entirely using integer division. I.e. fractional remainders are dropped. For any given node index N, the children of that node will always be in locations 2N+1 and 2(N+1) in the same array.

Therefore, The parent of any node N > 0 in such an array will always be at index (N-1)/2.

Parent to Child Examples:

Parent 0: children 1,2
Parent 1: children 3,4
Parent 2: children 5,6
Parent 3: children 7,8
etc...

Child to Parent Examples:

Child 8 : Parent = (8-1)/2 = 7/2 = 3
Child 7 : Parent = (7-1)/2 = 6/2 = 3
Child 6 : Parent = (6-1)/2 = 5/2 = 2
Child 5 : Parent = (5-1)/2 = 4/2 = 2

So for your problem:

(4999-1)/2 = 4998/2 = 2499

Note: remember this, since you'll be using it extensively when you start coding array-based heap-sort algorithms.

Answer 2

Thanks for all your help guys. And I found the answer to my question!

The general algorithm for finding the location of the parent node is:

[i + (root - 1)] / 2 where i is the location of the given node and root is the location of the root. So in the given problem above the root starts at position 0. so the equation to find the parent node of any node is [i + (0 - 1)] / 2 = (i - 1) / 2

Now let's say the root started at position 3, then the equation would be [i + (3 - 1)] / 2 = (i + 2) / 2!!!! This is the algorithm I needed. Most of you helped me solve the one problem i provided but i actually needed the general solution for a binary tree whose root can start at any postions; not just at zero