title: Traversing a tree in a special way
body: <p>We have a binary tree </p>
  
  <pre><code>type 'a tree = Node of 'a * 'a tree * 'a tree | Null ;;
  </code></pre>
  
  <p>We want to return an <code>'a list</code> containing all vertices in a specific order, i.e. the distance between two adjacent vertices in the list may not exceed 3. Each vertex can only appear once.</p>
  
  <p>Example. For the tree</p>
  
  <pre><code>      1
       / \
      2   6
     /
    3
   / \
  4   5
  </code></pre>
  
  <p>one possible answer is <code>[1; 3; 4; 5; 2; 6]</code></p>
  
  <p>For the time being I have the following code:</p>
  
  <pre><code>let walk t =
      let rec pom_walk t acc end_root = (* it's symmetric, so it could be start_root and the result would be correct too *)
          match t with
          | Null -&gt; acc
          | Node (nr, l, r) -&gt;
              if end_root then
                  nr::(pom_walk r (pom_walk l acc false) false)
              else
                  (pom_walk r (pom_walk l acc true) true) @ [nr]
       in
          pom_walk t [] true 
  </code></pre>
  
  <p>but this code has square complexity due to the usage of the <code>@</code> operator, which is linear itself.</p>
  
  <p>How can I solve this in linear time?</p>