title: How to build a Full Binary Tree dynamically?
body: <p>I'm currently trying to come up with an algorithm to implement full binary trees (binary trees with 
  either two or no children) dynamically.
  The code will be implemented in C++. I can implement my trees by hand, but as I have about 
  900 different trees I need to do this automatically. And here I need some ideas, hints and help.</p>
  
  <p>Let's start to explain what I'm doing:
  I get my trees from a graph merging process. I merge two nodes in a graph based on a cost function. The label of the
  bigger node will be the label of the merged node (my graphs nodes have a spatial size).
  So I end up with a vector which contains the merged nodes 
  and the remaining label for the new node (Note that the remaining label is based on the node size and
  not related to the note number). The last two entries in the vector are the first nodes which merge together. The next
  higher entry is the remaining label for the merged node. This continues in this order until just the root node (first entry)
  is left. </p>
  
  <p>The first problem is, my graphs have a different amount of nodes. So my
  trees from the merging process have different sizes, i.e. my vector has a different size.</p>
  
  <p>To give you an idea what this looks like, see the following example:</p>
  
  <p>treelist vector (the numbers on the left side, so a one dimensional vector):</p>
  
  <pre><code>27| root    (0)--&gt; root (27 and 33 are merged, remaining label is 27)
  33| right   (1)     
  27| left    (2)
  27| subroot (3)--&gt; t1   (3 and 27 are merged, remaining label is 27)
  27| right   (4)
  3 | left    (5)
  27| subroot (6) --&gt; t2  (10 and 27 are merged, remaining label is 27)
  27| right   (7)
  10| left    (8)
  27| subroot (9) --&gt; t3  (17 and 27 are merged, remaining label is 27)
  27| right   (10)
  17| left    (11)
  33| subroot (12)--&gt; t4  (31 and 33 are merged, remaining label is 33)
  33| right   (13)
  31| left    (14)
  </code></pre>
  
  <p>Tree build by the above treelist vector in ASCII format:</p>
  
  <pre><code>            root
               27
             /    \
         27(t1)   33(t4)
        /   \     /   \
       3  27(t2) 31    33
          /   \ 
        10   27(t3)
              / \
            17   27
  </code></pre>
  
  <p>Again, the actual vector I have is just the numbers on the left side. The words left/right refers 
  to the side of which its connected to the root/subroot. The number in the brackets are the 
  relative position in the vector.</p>
  
  <p>There are two rules which my trees are following:</p>
  
  <ul>
  <li>t1 is always connected to the root</li>
  <li>tk-1 is never a lower connection of tk, e.g. t1 is never the lower connection of t2</li>
  </ul>
  
  <p>What I want to do now is to create a general algorithm to build trees like the above with 
  different sizes (up to about 15-20). Size refers here to the amount of internal nodes, for the
  tree above it would be 4. </p>
  
  <p>My idea is/was to create these trees by a switch-case for the given treesize. 
  Unfortunately, I end up with the a lot of if-statements within these cases and for higher 
  cases its almost not managable anymore.</p>
  
  <p>See my pseudo algorithm for the general case below (trees are build bottom up):</p>
  
  <pre><code>PseudoCode: (Note that for building the tree the first insert is the left node and the second is the right node)
  switch(treesize)
          case 3: root = vector[0];   //represents root node
                  t1 = vector[3];     //represents t1
                  t2 = vector[6];     //represents t2
                  t3 = vector[9];     //represents t3
  
                  // create node t3 
                  t3-&gt;insert(vector[11]); t3-&gt;insert(vector[10]);
  
                  // create node t2
                  if (t3 == vector[8]) {t2-&gt;addChild(t3); t2-&gt;insert(vector[7]);} 
                  if (t3 == vector[7]) {t2-&gt;insert(vector[8]); t2-&gt;addChild(t3);} 
                  else {t2-&gt;insert(vector[8]); t2-&gt;insert(vector[7]);}            
  
                  // create node t1
                  if (t3 == vector[5] &amp;&amp; t2 != vector[4]) {t1-&gt;addChild(t3); t2-&gt;insert(vector[4]);} 
                  if (t3 == vector[4] &amp;&amp; t2 != vector[5]) {t1-&gt;insert(vector[5]); t1-&gt;addChild(t3);}
                  if (t2 == vector[5] &amp;&amp; t3 != vector[4]) {t1-&gt;addChild(t2); t1-&gt;insert(vector[4]);}
                  if (t2 == vector[4] &amp;&amp; t3 != vector[5]) {t1-&gt;insert(vector[5]); t1-&gt;addChild(t2);}
                  if (t3 == vector[5] &amp;&amp; t2 == vector[4]) { t1-&gt;addChild(t3); t1-&gt;addChild(t2);}
                  if (t2 == vector[5] &amp;&amp; t3 == vector[4]) { t1-&gt;addChild(t2); t1-&gt;addChild(t3);}
                  else {t1-&gt;insert(vector[5]); t1-&gt;insert(vector[4]);}
  
                  // create root (Note that t1 is always connected to the root)
                  if (t3 == vector[2]) {root-&gt;addChild(t3); root-&gt;addChild(t1);}
                  if (t2 == vector[2]) {root-&gt;addChild(t2); root-&gt;addChild(t1);}
                  if (t3 == vector[1]) {root-&gt;addChild(t1); root-&gt;addChild(t3);}
                  if (t2 == vector[1]) {root-&gt;addChild(t1); root-&gt;addChild(t2);}
                  if (t1 == vector[2] &amp;&amp; (t3 &amp;&amp; t2) != vector[1]) {root-&gt;addChild(t1); root-&gt;insert(vector[1]);
                  if (t1 == vector[1] &amp;&amp; (t3 &amp;&amp; t2) != vector[2]) {root-&gt;insert(vector[2]); root-&gt;addChild(t1);}
  
  
          case 4: root = vector[0];   //represents the root node
                  t1 = vector[3];     //represents t1
                  t2 = vector[6];     //represents t2
                  t3 = vector[9];     //represents t3
                  t4 = vector[12];    //represents t4
  
                  // create t4
                  t4-&gt;insert(vector[14]); t3-&gt;insert(vector[13]);
  
                  // create t3
                  if (t4 == vector[11]) {t3-&gt;addChild(t4); t3-&gt;insert(vector[10]);}
                  if (t4 == vector[10]) {t3-&gt;insert(vector[11]); t3-&gt;addChild(t4);}
                  else {t3-&gt;insert(vector[11]); t3-&gt;insert(vector[10]);}
  
                  // create t2
                  if (t4 == vector[8] &amp;&amp; t3 != vector[7]) {t2-&gt;addChild(t4); t2-&gt;insert(vector[7]);}
                  if (t4 == vector[7] &amp;&amp; t3 != vector[8]) {t2-&gt;insert(vector[8]); t2-&gt;addChild(t4);} 
                  if (t3 == vector[8] &amp;&amp; t4 != vector[7]) {t2-&gt;addChild(t3); t2-&gt;insert(vector[7]);}
                  if (t3 == vector[7] &amp;&amp; t4 != vector[8]) {t2-&gt;insert(vector[8]); t2-&gt;addChild(t3);}
                  if (t4 == vector[8] &amp;&amp; t3 == vector[7]) {t2-&gt;addChild(t4); t2-&gt;addChild(t3);}
                  if (t3 == vector[8] &amp;&amp; t4 == vector[7]) {t2-&gt;addChild(t3); t2-&gt;addChild(t4);}
                  else {t2-&gt;insert(vector[8]); t2-&gt;insert(vector[7]);}
  
                  // create t1
                  if (t4 == vector[5] &amp;&amp; t3 != vector[4] &amp;&amp; t2 != vector[4]) {t1-&gt;addChild(t4); t1-&gt;insert(vector[4]);}
                  if (t4 == vector[4] &amp;&amp; t3 != vector[5] &amp;&amp; t2 != vector[5]) {t1-&gt;insert(vector[5]); t1-&gt;addChild(t4);} 
                  if (t3 == vector[5] &amp;&amp; t4 != vector[4] &amp;&amp; t2 != vector[4]) {t1-&gt;addChild(t3); t1-&gt;insert(vector[4]);}
                  if (t3 == vector[4] &amp;&amp; t4 != vector[5] &amp;&amp; t2 != vector[5]) {t1-&gt;insert(vector[5]); t1-&gt;addChild(t3);}
                  if (t2 == vector[5] &amp;&amp; t4 != vector[4] &amp;&amp; t3 != vector[4]) {t1-&gt;addChild(t5); t1-&gt;insert(vector[4]);}
                  if (t2 == vector[4] &amp;&amp; t4 != vector[5] &amp;&amp; t3 != vector[5]) {t1-&gt;insert(vector[5]); t1-&gt;addChild(t2);}
                  if (t4 == vector[5] &amp;&amp; t3 == vector[4]) {t1-&gt;addChild(t4); t1-&gt;addChild(t3);}
                  if (t4 == vector[5] &amp;&amp; t2 == vector[4]) {t1-&gt;addChild(t4); t1-&gt;addChild(t2);}
                  if (t3 == vector[5] &amp;&amp; t2 == vector[4]) {t1-&gt;addChild(t3); t1-&gt;addChild(t2);}
                  if (t3 == vector[5] &amp;&amp; t4 == vector[4]) {t1-&gt;addChild(t3); t1-&gt;addChild(t4);}
                  if (t2 == vector[5] &amp;&amp; t3 == vector[4]) {t1-&gt;addChild(t2); t1-&gt;addChild(t3);}
                  if (t2 == vector[5] &amp;&amp; t4 == vector[4]) {t1-&gt;addChild(t2); t1-&gt;addChild(t4);}
  
                  // create root (Note that t1 is always connected to the root)
                  if (t4 == vector[2]) {root-&gt;addChild(t4); root-&gt;addChild(t1);}
                  if (t3 == vector[2]) {root-&gt;addChild(t3); root-&gt;addChild(t1);}
                  if (t2 == vector[2]) {root-&gt;addChild(t2); root-&gt;addChild(t1);}
                  if (t4 == vector[1]) {root-&gt;addChild(t1); root-&gt;addChild(t4);}
                  if (t3 == vector[1]) {root-&gt;addChild(t1); root-&gt;addChild(t3);}
                  if (t2 == vector[1]) {root-&gt;addChild(t1); root-&gt;addChild(t2);}
                  if (t1 == vector[2] &amp;&amp; (t4 &amp;&amp; t3 &amp;&amp; t2) != vector[1]) {root-&gt;addChild(t1); root-&gt;insert(vector[1]);}
                  if (t1 == vector[1] &amp;&amp; (t4 &amp;&amp; t3 &amp;&amp; t2) != vector[2]) {root-&gt;insert(vector[2]); root-&gt;addChild(t1);}
  
          case 5: .....
  
          ....
          ....
  </code></pre>
  
  <p>As you notice this will be a mess for higher cases. </p>
  
  <p>So I always have to check if the left or right node is maybe a connection to
  one of the subroots. This actually causes all these if-statements.</p>
  
  <p>My question now is: Do you have any idea how to implement this algorithm in a better fashion or even totally different?
  Any advice on this is helpful.</p>
  
  <p>Thank you very much in advance for any help. </p>
  
  <p>Let me know if something is not clear or if I should give a second example.</p>
  
  <h2>See below how I get my Vector from my graph:</h2>
  
  <p>Graph:</p>
  
  <p><a href="https://i.stack.imgur.com/X90Qt.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/X90Qt.jpg" alt="enter image description here"></a></p>
  
  <p>My cost function to merge two nodes is C = Node_A + Node_B / Edgeweight. </p>
  
  <p>Merging process:<br>
  1. 12+6 -> 6<br>
  2. 24+31 -> 24<br>
  3. 6+24 -> 6<br>
  4. 6+9 -> 6<br>
  5. 6+22 -> 6  </p>
  
  <p>Resulting Vector (same properties as above) and Tree:  </p>
  
  <pre><code>(Note that the first two nodes which merges are the last two entries)
  6   --&gt; root                                   root
  22                                              6
  6                                             /   \
  6   --&gt; t1                                 6(t1)   22
  9                                          /    \           
  6                                        6(t2)   9
  6   --&gt; t2                              /   \
  24                                    6(t4)  24(t3)
  6                                    /   \   /  \
  24  --&gt; t3                          6    12 24   31
  31 
  24
  6   --&gt; t4
  12
  6
  </code></pre>
  
  <p>Maybe there is also a more elegenat way to build my vector from the merging process to obtain my trees in the next step. </p>