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.