title: What's wrong with my tree traversal code?
body: <p>I have a simple tree, defined thusly:</p>
  
  <pre><code>type BspTree =
      | Node of Rect * BspTree * BspTree
      | Null
  </code></pre>
  
  <p>I can get a collection of leaf nodes (rooms in my tree "dungeon") like this, and it seems to work:</p>
  
  <pre><code>let isRoom = function
      | Node(_, Null, Null) -&gt; true
      | _ -&gt; false
  
  let rec getRooms dungeon =
      if isRoom dungeon then
          seq { yield dungeon }
      else
          match dungeon with
          | Node(_, left, right) -&gt;
              seq { for r in getRooms left -&gt; r
                    for r in getRooms right -&gt; r }
          | Null -&gt; Seq.empty
  </code></pre>
  
  <p>But now I'm trying to get sister leaf node rooms so I can connect them with corridors, and I'm failing miserably (as I often do). Here's my attempt:</p>
  
  <pre><code>let rec getCorridors dungeon =
      match dungeon with
      | Null -&gt; failwith "Unexpected null room"
      | Node(_, left, right) -&gt;
          match left, right with
          | Null, Null -&gt; Seq.empty
          | Node(leftRect, _, _), Node(rightRect, _, _) -&gt;
              if isRoom left &amp;&amp; isRoom right
              then seq { yield makeCorridor leftRect rightRect }
              else seq { for l in getCorridors left -&gt; l
                         for r in getCorridors right -&gt; r }
          | _ -&gt; failwith "Unexpected!"
  </code></pre>
  
  <p>I just end up with an empty seq. Anyway, this all hurts my brain, and I know it's unlikely anyone will slog through it, but I figured it wouldn't hurt to ask.</p>