title: nested set binary tree, query leftmost and rightmost nodes
body: <p>I have a MySQL table storing a binary tree in a nested set model with some extra properties. The binary tree is neither full nor complete, so there may be nodes on the middle with only one child. </p>
  
  <p>It looks something like this (but with much more data):</p>
  
  <pre><code>+----+------+-------+-----------+-------+----------+--------------------+
  | id | left | right | parent_id | level | position | number_of_children |
  +----+------+-------+-----------+-------+----------+--------------------+
  |  1 |    1 |     8 | NULL      |     1 | LEFT     |                  3 |
  |  2 |    2 |     3 | 1         |     2 | LEFT     |                  0 |
  |  3 |    4 |     7 | 1         |     2 | RIGHT    |                  1 |
  |  4 |    5 |     6 | 2         |     3 | LEFT     |                  0 |
  +----+------+-------+-----------+-------+----------+--------------------+
  </code></pre>
  
  <p>How could I query the <strong>leftmost</strong> or the <strong>rightmost</strong> node of a tree or sub-tree?</p>
  
  <p>Some graphic explanation: <a href="https://imgur.com/w7gxtOC" rel="nofollow noreferrer">https://imgur.com/w7gxtOC</a></p>
  
  <p>I tried it multiple ways, but these are not working on all scenarios (these are examples for the leftmost):</p>
  
  <pre><code>SELECT * FROM nodes
    WHERE position = 'LEFT' 
      AND number_of_children &lt; 2
    HAVING `right` = `left` + 1
    ORDER BY element.`left` ASC
    LIMIT 1;
  </code></pre>
  
  <p>Or this one, it definitely finds the solution but finds some false ones too:</p>
  
  <pre><code>SELECT * FROM nodes AS element
    JOIN nodes AS upline ON element.parent_id = upline.id
    WHERE upline.position = 'LEFT'
      AND element.position = 'LEFT'
      AND element.number_of_children &lt; 2
    ORDER BY element.`left` ASC;
  </code></pre>