9

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.

Vadim Kotov
  • 8,084
  • 8
  • 48
  • 62
user2188910
  • 141
  • 1
  • 1
  • 5
  • 2
    You should write out exactly what you tried. There may be a simple error somewhere. – Austin Mullins Mar 20 '13 at 01:08
  • As specified, this question is impossible. You must have misunderstood or misremembered. I can immediately think of ways that both 4998 and 5000 are the answer. – Mooing Duck Mar 20 '13 at 01:10
  • no. The expression that will give me the location of any child's parent will be in the form of "2^(n+1) - 1" or something like that. Then you put in the location of the child (4999 in this case) and the expression should give you the location of the parent node. – user2188910 Mar 20 '13 at 01:18
  • I don't really need to know how to solve this problem. I need more of a strategy to find an algorithm or equation like the one above that will give me the location of the parent node. She said she will give us a binary tree implemented as an array. The root of the binary tree could start at index 0 of the array or at 99. My job is to find an equation such that when you plug in the location of a child node, it will produce the location of the parent node. I hope i'm making sense here – user2188910 Mar 20 '13 at 01:19
  • @MooingDuck: Really? There are 2^k elements in the k-th row, so we can map 4999 back to the tree location, get the tree location of the parent, and then map that back to array index, surely? Why would there be ambiguity in the result? – Oliver Charlesworth Mar 20 '13 at 01:21
  • ^ huh??? can you please try to answer my question. – user2188910 Mar 20 '13 at 01:28
  • @OliCharlesworth: oh, I totally missed the "one level at a time". From left to right would have been totally ambiguous. My bad. Either way, unless "missing" nodes are also put in the array, this is still unsolvable. If they are put in the array, the answer to this question is very trivial. – Mooing Duck Mar 20 '13 at 05:22

5 Answers5

19

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.

WhozCraig
  • 65,258
  • 11
  • 75
  • 141
3

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

user2188910
  • 141
  • 1
  • 1
  • 5
2

It seems this is how the array elements map back to tree based on array indices

     0
  1     2
3   4 5   6

If so, then the parent of index n is at floor( (n - 1) / 2 ) (for n != 0)

Arun
  • 19,750
  • 10
  • 51
  • 60
1

If you do the log2 of the number requested (4999) and take the integer part it will give you the closest power of two to the number (12). It is 2^12 = 4096.

The parent of the nodes between 4096 and 2^13 - 1, are the ones between 2^11 and 2^12 - 1. And for each pair of nodes in the first range you have its parent in the second. So you can map them taking the integer part of the half of the difference (4999 - 4096) and adding it to the parent range start (2048).

So you will have floor of 903 / 2, and add it to 2048, getting 2499.

Note that I didn't make a precise calculation, take the strategy of the answer not the results.

You can put this algorithm in a mathematical expression, with a little work.

Hope it helps!

nico
  • 110
  • 2
  • 8
  • good. you got the right answer so you know what I'm asking here. Now i just have to carefully read what you said and try to understand your strategy lol. thanks for the reply. – user2188910 Mar 20 '13 at 01:42
  • 1
    @nico while your answer is 100% correct, (strategy, I didn't check the edge cases), there is a _very_ simple equation which should give the same answer. – Mooing Duck Mar 20 '13 at 05:24
-1

The parent node is at n/2 if n is even. It is at (n-1)/2 if n is odd. So you can remember it as math.ceil((n-1)/2)

Amogh Godbole
  • 1
  • 1
  • 1