Binary Tree represented using array

Question

Consider the following array, which is claimed to have represented a binary tree:

[1, 2, 5, 6, -1, 8, 11]

Given that the index with value -1 indicates the root element, I've below questions:

a) How is this actually represented?

Should we follow below formulae (source from this link) to figure out the tree? Three simple formulae allow you to go from the index of the parent to the index of its children and vice versa:

* if index(parent) = N, index(left child) = 2*N+1
* if index(parent) = N, index(right child) = 2*N+2
* if index(child) = N, index(parent) = (N-1)/2 (integer division with truncation)

If we use above formulae, then index(root) = 3, index(left child) = 7, which doesn't exist.

b) Is it important to know whether it's a complete binary tree or not?

Answer 1

N=0 must be the root node since by the rules listed, it has no parent. 0 cannot be created from either of the expressions (2*N + 1) or (2*N + 2), assuming no negative N.

Note, index is not the value stored in the array, it is the place in the array. For [1, 2, 5, 6, -1, 8, 11] Index 0 = 1 Index 1 = 2 Index 2 = 5, etc.

If it is a complete tree, then -1 is a valid value and tree is

    1  
   /  \  
  2    5  
 / \  / \  
6 -1 8  11  

-1 could also be a "NULL" pointer, indicating no value exists at that node.

So the Tree would look like

    1  
   / \  
  2   5  
 /   / \  
6   8  11