Select recursive in mysql data hierarchy

Question

How to build a mysql function or recursive query to bring the last descending of a specific side of a binary tree?

Satisfying a binary tree, each node can have only two branches, one left and one right.

How to pick up in a query the last descendant of a branch on the right side?

For example:

           a 
     b           c
  d     e     f     g
 h     j k         z x

In this dataset, the last descendant of "a" on the right is the letter "x", and on the left the letter "h". To get to 'h', went through 'b' and’d', starting from 'a' and 'lft'.

The last descendant of "b" on the right is the letter "k", the left is the letter "h".

Like, the last descendant of "e" on the right is the letter "k", but the left is the letter "j".

Each letter(node) of this tree has the normal structure of a tree in nested sets or Nested Set Model, to meet other system needs.

That is, the fields id, parent_id, left, right.

And beyond these, the kind field Enum: growth_to('lft','rgt'), to indicate whether the child was raised left or right.

For example:

b.growth_on = lft
c.growth_on = rgt

With respect to his father ("a"), node "b" grew to the left, and node "c" to the right.

I need to create a recursive mysql function where I enter the parent id, and the side(lft or rgt) I want to fetch the last descendant and it returns me the corresponding letter and its properties, or even only id.

I know that I could control the placement of the node below your father, just by moving the correct indices, but when a knot has only one child, I need to know if he is right or left, even if there is only one, he needs to possess a "side".

I think the logic would be to create a recursive condition within the mysql function.

To find the last descending node of "a" on the right, inform the id of "a" and growth_on = 'lft'

So inside a loop: (that’s the part I don’t know how to do with mysql functions)

where children.parent_id = a.id && children.growth_on = 'lft'

Answer 1

The following precedent receives the ID of the initial node, the "side" you want to check and returns the id of the last found descendant, or the initial node itself if it has no offspring on the specified side :

DELIMITER //
CREATE PROCEDURE find_leaf(IN n_id VARCHAR(10), IN side VARCHAR(10), OUT child VARCHAR(10))
BEGIN
  IF side = 'left' THEN
    SET child = (SELECT leftN FROM node WHERE id=n_id);
  ELSE
    SET child = (SELECT rightN FROM node WHERE id=n_id);
  END IF;

  IF child IS NOT NULL THEN
    CALL find_leaf(child, side, child);
  ELSE 
    SET child = n_id;
  END IF;
END //

You can see the working process here http://sqlfiddle.com/#! 2/be812/3

Note that this is not the best possible solution, just a (functional) outline of the idea. In addition to recursion procedures is disabled by default in mysql (and it is not possible in functions, only procedures), so the invocation must be something similar to this:

SET max_sp_recursion_depth=255; -- habilita recursão, 255 é o nível máximo permitido
CALL find_leaf('a', 'rigth', @leaf);
SELECT @leaf;
CALL find_leaf('e', 'left', @leaf);
SELECT @leaf;

Note: the schema I used may be a little different from yours, but it should be simple to adapt:

CREATE TABLE node(
id VARCHAR(10) PRIMARY KEY, 
parent_id VARCHAR(10) DEFAULT NULL, 
leftN VARCHAR(10) DEFAULT NULL, 
rightN VARCHAR(10) DEFAULT NULL,
growth_on ENUM('left', 'right') DEFAULT NULL
) ENGINE=INNODB;