CareerCup

Would you give an example.

a) did you mean value inside each array element refers to parent? (i.e. index = node number and value = parent number)
b) if answer to a) is no, i.e. index = parent number and value = node number, then root node should have a value = index and not -1. otherwise its parent will be the node with number equal to root's index number.

Just to clarify, does that mean, every node in the tree has exactly one child?

is It a heap? If so, there is not need to recreated:

Parent of node i = i/2
Left node for node i = i*2
Right node for node i = (i*2) + 1