Array Representation of a Complete Binary Tree

The binary tree is ubiquitous in Computer Science, being especially useful for storing data in a way that allows for efficient access and operations. The question to be addressed in this post is: how to implement a binary tree?  

Like a List ADT, a binary tree may be implemented as a linked list or as an array, the more intuitively straightforward being the linked list implementation.

Pythonically, one can imagine a crude implementation based on Python dict:

child0 = { 'data': 4,

                 'child0': None,

                 'child1': None }

child1 = { 'data': 5,

                 'child0': None,

                 'child1': None }

root = { 'data': 3, 

               'child0': child0,

               'child1': child1 }

or with C/C++ struct, as follows

struct Node {

          int data;

          Node * child0;

          Node * child1;

   };

But if we can put it all in a straightforward array, like as follows, it would be better:

There wouldn't be any need to store pointers or references in each node. It means less memory consumed...

The tricky part in putting it all into an array is the indexing... Consider the following binary tree:

Suppose we lay the nodes out in the array in a breadth-first manner, as follows:

Note that 4 and 5 are the children of node 3, 6 and 7 that of  4.  Can you see any pattern here? 

Node 4 is in index 2(0) + 1 = 2.

Node 5 in index 2(0) + 2 = 2..

Node 6 is stored in index 2(1) + 1 = 3.

Node 7 in index 2(1) + 2 = 4.

Hmm...

Let's try with a full binary tree:

Laying it out linearly in a breadth-first manner, we have:

And it does seem that the formula work..

Given a node at index n, its first child will be at 2n + 1, and the second one at 2n + 2.

So far, it works with a complete binary tree.  Will it work with one that is incomplete?

And how do we get the parent of a node? Can you work it out?