title: Haskell: Flatten binary tree
body: <p>I was thinking about flattening a binary tree to a list, for latter processing.</p>
  
  <p>I first thought of using <code>(++)</code> to join the left and right branches, but then thought in the worse case that would take <code>O(n^2)</code> time.</p>
  
  <p>I then thought of building the list backwards, using <code>(:)</code> to append to the front in linear time. However, then I thought if I send this list to a fold-like function, it has to wait until the entire tree is traversed before it can begin folding, and hence can't use <a href="http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/rewrite-rules.html#id3189202">list fusion</a>.</p>
  
  <p>I then came up with the <a href="http://ideone.com/1oCjH">following</a>:</p>
  
  <pre><code>data Tree a = Node a (Tree a) (Tree a) | Tip
  
  flatten :: Tree a -&gt; [a]
  flatten x = (flatten' x) []
  
  flatten' :: Tree a -&gt; [a] -&gt; [a]
  flatten' (Node x left right) l = (flatten' left (x:(flatten' right l)))
  flatten' Tip l = l
  
  main = 
    putStrLn $ show $ flatten $ 
      (Node 2 (Node 1 Tip Tip) (Node 4 (Node 3 Tip Tip) Tip))
  </code></pre>
  
  <p>Will this work in <code>O(n)</code> time, take "stack space" no more than proportional to the greatest depth of the tree and can it be fused with a consuming function (i.e. intermediate list eliminated)? Is this the "correct" way to flatten a tree?</p>