title: Binary tree traversal to enumerate all permutations of Fibonacci values
body: <p>I'm on-going working on this project as an interest, and keep coming back to it...</p>
  
  <p>What I'm trying to create is an algorithm to enumerate sets of values of the binary tree of Fibonacci values:</p>
  
  <p><img src="https://i.stack.imgur.com/Wkwnw.jpg" alt="Fibonacci tree values"></p>
  
  <p>The algorithm I'd use to print permutations of this tree:</p>
  
  <ol>
  <li>Print root value (Result: ([root 0]=5))</li>
  <li>descend to left child [left 1]</li>
  <li>Print new left node [left 1], and right sibling node value (Result: ([left 1] 3,[right 1] 2))</li>
  <li>If right sibling node [right 1], has child nodes, traverse this right node [right 1], enumerating it's values, along with it's sibling left node [left 1] (Result: [left 1] 3,[left 3] 1,[right 3] 1)</li>
  <li>Descend to left child [left 2], as step 2</li>
  <li>Print new left node value [left 2] 2, and right sibling node value [right 2] 1 of common left parent [left 1]; whilst traversing and enumerating the result of each level of right node of root. So in the about tree example, the enumerated result would be, traversing the tree to get the permutations: ([left 2] 2,[right 2] 1,[right 1] 2),([left 2] 2,[right 2] 1, [left 3] 1, [right 3] 1))</li>
  <li>No left child to decend into, so stop</li>
  </ol>
  
  <p>Each set should add up to value of root. I think my approach for trying to describe each step in the algorithm is potentially not fully clear - any help on best practice for writing out steps in an algorithm would also be useful to me.</p>
  
  <p>The results I'd expect here, enumerating the tree above would be:</p>
  
  <p>([root 0] 5),([left 1] 3, [right 1] 2),([left 1] 3, [left 3] 1, [right 3] 1),([left 2] 2, [right 2] 1, [right 1] 2),([left 2] 2,[right 2] 1, [left 3] 1, [right 3] 1)</p>
  
  <p>I'd like to take a recursive approach and incorporate, as a method, into the Class of binary structure I've created that builds the tree. So this isn't about building the tree structure but traversing it as per the method above, or a method that yields the same results.</p>
  
  <p>Could anyone help me further? Any help would be much appreciated.</p>
  
  <h1>Adding in sets printing method to my `FibTree` `Class`:</h1>
  
  <h2>FibTree Header file (code snippets):</h2>
  
  <pre><code>class FibTree {
  
  public:
      class Node {
      public:
      int data;
          Node const* left;
          Node const* right;
          Node const* parent;
          int n;
          int level;
          int index;
  
          Node (void);
  
      };
  
      Node const* root; // 'root' pointer to constant Node
      FibTree (int);
      Node const* getRoot(void);
  
      void startWriteSets(Node const* root); // Write all sets of tree
  
  private:
      static Node* buildTree( int n, int level = 0, int i = 1, Node* parent = NULL );
      // Used by startWriteSets
      void writeSets(std::vector&lt;Node const*&gt; &amp;setsList, Node const* cur);
  </code></pre>
  
  <h2>FibTree CPP file (code snippets):</h2>
  
  <pre><code>// FibTree Constructor
  FibTree::FibTree(int n) {
      this-&gt;root = buildTree( n );
  };
  
  // Getters
  FibTree::Node const* FibTree::getRoot(void) {
      return this-&gt;root;
  }
  
  // Write sets of tree
  void FibTree::startWriteSets(Node const* root) {
      std::vector&lt;Node const*&gt; setsList;
      std::cout &lt;&lt; root-&gt;data;
      writeSets(setsList, root);
  }
  
  // Private FibTree methods
  FibTree::Node* FibTree::buildTree( int n, int level, int i, Node* parent ) { // Build Tree structure
      Node* thisNode = new Node();
      thisNode-&gt;n = n;
      thisNode-&gt;level = level;
      thisNode-&gt;index = i;
      thisNode-&gt;parent = parent;
      if (n &lt; 2) {
           thisNode-&gt;left = NULL;
           thisNode-&gt;right = NULL;
           thisNode-&gt;data = n;
           return thisNode;
      } else {
           thisNode-&gt;left = buildTree( n - 1 , level + 1, i*2, thisNode );
           thisNode-&gt;right = buildTree( n - 2, level + 1, i*2+1, thisNode );
           thisNode-&gt;data = thisNode-&gt;left-&gt;data + thisNode-&gt;right-&gt;data;
           return thisNode;
      }
  }
  
  void FibTree::writeSets(std::vector&lt;Node const*&gt; &amp;setsList, Node const* cur) {
      std::vector&lt;Node const*&gt;::iterator nodeIterator;
  
      // Displays all preceding left values
      for (nodeIterator = setsList.begin();
          nodeIterator != setsList.end(); nodeIterator++) {
          std::cout &lt;&lt; *nodeIterator-&gt;data;
      }   
      std::cout &lt;&lt; cur-&gt;left-&gt;data;
      std::cout &lt;&lt; cur-&gt;right-&gt;data;
  
      setsList.push_back(cur-&gt;left);
      writeSets(setsList,cur-&gt;right);
      setsList.pop_back();
  }
  
  
  // FibTree Node constructor
  FibTree::Node::Node()
  : data( 0 ),
  left( NULL ),
  right( NULL ),
  parent( NULL ),
  n( 0 ),
  level( 0 ),
  index( 0 )
  {
  };
  </code></pre>
  
  <p><strong>I'm getting a compile error on <code>std::cout &lt;&lt; *nodeIterator-&gt;data;</code> within <code>void FibTree::writeSets</code> reports:</strong> <blockquote>_error: request for member 'data' in '* nodeIterator. __gnu_cxx::__normal_iterator&lt;_Iterator, _Container>::operator-> with _Iterator = const FibTree::Node**, <em>Container = std::vector >', which is of non-class type 'const FibTree::Node*'</em></blockquote></p>
  
  <p>Any help tracing this error would be greatly appreciated!</p>