title: Breadth-first-search traverse the binary tree with unknown height
body: <p>I'm trying to implement an algorithm (Breadth-first-search or Depth-first-search) to traverse and extract data from a binary tree (with 2 direction WIN or LOSE) with UNKNOWN DEEP LEVEL (it can be up to 80-90). </p>
  
  <p>What I need is all the paths as well as content of each node from root to leaves. I'm trying to find some way to trace the path, not only current path but all possible paths. And because whenever we finish at a leaf, we need to start again from root, we need way to check to see if :</p>
  
  <ul>
  <li>The path has been traversed before or not? (use queues or stacks????)</li>
  <li>Where does it stop? so we can pick up and continue from that (use flag to check???)</li>
  </ul>
  
  <p>The tree:</p>
  
  <p><img src="https://i.stack.imgur.com/JlK8F.png" alt="http://i59.tinypic.com/zkiznm.jpg"></p>
  
  <p>So what I need to do is find all posible path from root A to leaves (V, Y, X, Q, Z, P, O, J, E, I, T, S, M)</p>
  
  <p>And all possbile paths will be:</p>
  
  <pre><code>A -&gt; C -&gt; G -&gt; L -&gt; R -&gt; V
  A -&gt; C -&gt; G -&gt; L -&gt; R -&gt; U -&gt; Y
  A -&gt; C -&gt; G -&gt; L -&gt; R -&gt; U -&gt; X
  A -&gt; C -&gt; G -&gt; L -&gt; Q
  A -&gt; C -&gt; G -&gt; Z
  A -&gt; C -&gt; F -&gt; K -&gt; P
  A -&gt; C -&gt; F -&gt; K -&gt; O
  A -&gt; C -&gt; F -&gt; J
  A -&gt; B -&gt; E
  A -&gt; B -&gt; D -&gt; I
  A -&gt; B -&gt; D -&gt; H -&gt; N -&gt; T
  A -&gt; B -&gt; D -&gt; H -&gt; N -&gt; S
  A -&gt; B -&gt; D -&gt; H -&gt; M
  </code></pre>
  
  <p>Each node will have data I need to extract. </p>
  
  <p>When we go to the leave, we will need to start over from the beginning, but we need to find some way to keep track of the paths we have traverse so we don't have to do it again since the height of the tree is not just 7 levels like this example, it may up to 80-100. </p>
  
  <p><strong>#EDITED</strong>
  The reason I want to use BFS instead of DFS is because I want to avoid reaching at the leave level soon, since i will need to start at the beginning after that. If it haven't reach to the leave, it will be much easier to get as much data as possible, to build the tree. </p>
  
  <p>I still thinking about the algorithm but I stucked:</p>
  
  <p>Pseudo code:</p>
  
  <pre><code>Create an empty tree
  Create an empty queue to keep track of nodes that need to be processed.
  Create an empty arrray of array (A) to save path. This array will be built up with each child     array is a possible path:
  [ [WIN,WIN,WIN,WIN,WIN,LOSE,WIN,LOSE,LOSE,LOSE,LOSE],
    [WIN,WIN,WIN,WIN,WIN,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,],
  .............................................................................................
    [LOSE,LOSE,LOSE,LOSE,WIN,LOSE]]
  Create an empty arrray of array (B) to save flag. This array will have exact size with A but it will have 2 value 0 when we haven't visit that node, 1 when we visit it). So this array will change value from 0 to 1 when we visit node.
  [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 0, 0, 0,],
  ....................................................
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
  
  Add the starting point to the tree as the root node
  Add the root node to a queue for processing
  
  Repeat until the queue is empty (or finish):
    Remove a node from the queue 
    For child value WIN: 
      If the child hasn't already been processed: 
        Add it to the queue 
        Add it to array of array A
        Set 1 to array of array B
        Create an edge in the graph that connects the node and its neighbor
  </code></pre>
  
  <p>Any help would be appreciate! Thanks a lot!</p>