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.

Accepted Answer

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.

Finding the location of a parent node in a binary tree

Solution

Problem