0

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.

It looks something like this (but with much more data):

+----+------+-------+-----------+-------+----------+--------------------+
| 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 |
+----+------+-------+-----------+-------+----------+--------------------+

How could I query the leftmost or the rightmost node of a tree or sub-tree?

Some graphic explanation: https://i.stack.imgur.com/pHozW.jpg

I tried it multiple ways, but these are not working on all scenarios (these are examples for the leftmost):

SELECT * FROM nodes
  WHERE position = 'LEFT' 
    AND number_of_children < 2
  HAVING `right` = `left` + 1
  ORDER BY element.`left` ASC
  LIMIT 1;

Or this one, it definitely finds the solution but finds some false ones too:

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 < 2
  ORDER BY element.`left` ASC;
balsa0
  • 1
  • 3
  • Have you looked into recursive queries? That's really the only way to handle tree structures. Try this: https://stackoverflow.com/questions/20215744/how-to-create-a-mysql-hierarchical-recursive-query – Without Haste Sep 22 '18 at 20:36
  • Thanks, I will take a look, but I try to avoid recursion if possible. Although this is a hybrid model with nested set and adjacency list properties, I'd like to stick to the nested sets, because the point of it would be to avoid recursion at all [wikipedia - nested set model](https://en.wikipedia.org/wiki/Nested_set_model) – balsa0 Sep 22 '18 at 20:44
  • If it is a nested set, how do you have value 3 on the both a left and a right (ids 2 and 3)? Maybe I don't understand the data structure. – Without Haste Sep 22 '18 at 20:50
  • Sorry, that was a mistake in my example, fixed it. – balsa0 Sep 23 '18 at 11:23
  • Is it possible for a node to be on the Right without a corresponding Left node? For instance, could Id 4 be labeled as Right? – Without Haste Sep 23 '18 at 13:03
  • Also, how does the table look if there is an odd number of elements? Would one of the "left" or "right" values be null? – Without Haste Sep 23 '18 at 13:08
  • Nodes always have left or right labels (positions). The binary tree is neither full nor complete, so there can be right nodes without left siblings, the example image shows just that. – balsa0 Sep 23 '18 at 17:38

0 Answers0