title: How to build an incomplete binary tree from array representation
body: <p>if the input is an array, where <code>null</code> means no node.</p>
  
  <p>input:</p>
  
  <p><code>[1, 2, 3, null, 5, null, 7]</code></p>
  
  <p>Please assume that I have already checked the input. </p>
  
  <p>For each <code>array[i]</code>, its parents <code>array[i / 2]</code> will not be <code>null</code> (recursively, so root can not be <code>null</code>).</p>
  
  <p>How to build a tree with such logic relation:</p>
  
  <pre><code>   1
   /    \
  2      3
   \      \ 
    5      7
  </code></pre>
  
  <p>each node should be represented by a <code>TreeNode</code> object:</p>
  
  <pre><code>class TreeNode {
  public:
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  };
  </code></pre>
  
  <p>I found a <a href="http://analgorithmaday.blogspot.com/2013/05/create-binary-tree-using-array.html" rel="noreferrer">blog here</a> where a complete tree was built</p>
  
  <p>but if the tree is incomplete as mentioned above, how to do it neatly and efficiently ?</p>
  
  <p>Test data:</p>
  
  <p>[input array]</p>
  
  <p><code>[-64,12,18,-4,-53,null,76,null,-51,null,null,-93,3,null,-31,47,null,3,53,-81,33,4,null,-51,-44,-60,11,null,null,null,null,78,null,-35,-64,26,-81,-31,27,60,74,null,null,8,-38,47,12,-24,null,-59,-49,-11,-51,67,null,null,null,null,null,null,null,-67,null,-37,-19,10,-55,72,null,null,null,-70,17,-4,null,null,null,null,null,null,null,3,80,44,-88,-91,null,48,-90,-30,null,null,90,-34,37,null,null,73,-38,-31,-85,-31,-96,null,null,-18,67,34,72,null,-17,-77,null,56,-65,-88,-53,null,null,null,-33,86,null,81,-42,null,null,98,-40,70,-26,24,null,null,null,null,92,72,-27,null,null,null,null,null,null,-67,null,null,null,null,null,null,null,-54,-66,-36,null,-72,null,null,43,null,null,null,-92,-1,-98,null,null,null,null,null,null,null,39,-84,null,null,null,null,null,null,null,null,null,null,null,null,null,-93,null,null,null,98]</code></p>