How to build a mysql function or recursive query to bring up the last descendant of a specific side of a binary tree?
Satisfying a binary tree, each node can have only two branches, one on the left and one on the right.
How can I get the last descendant of a branch on the right in a query?
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 is the letter "h". To get to 'h', it 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".
As well, the last descendant of "e" on the right is the letter "k", but the left is the letter "j".
That is, the
id, parent_id, left, right fields.
And besides these, the enum type field:
growth_to('lft','rgt') , to indicate if the child was created on the left or on the right.
b.growth_on = lft c.growth_on = rgt
With respect to its parent("a"), node "b" grew to the left, and node "c" to the right.
I need to create a mysql recursive function where I inform the parent's id, and the side (lft or rgt) that I want to get the last descendant and it returns me the corresponding letter and its properties, or even just the id.
I know I could control the placement of the node below its parent, just moving the correct indices, but when a node has only one child, I need to know if it is right or left, even if there is only one, it needs to have One side".
I think the logic would be, create a recursive condition inside the mysql function.
To look for the last node descending from "a" on the right, I would enter the
id of "a" and
growth_on = 'lft'
So inside a loop: (which is the part I don't know how to do with mysql functions)
where children.parent_id = a.id && children.growth_on = 'lft'
The following procedure receives the ID of the initial node, the "side" you want to check and returns the id of the last descendant found, or of the initial node itself if it has no descendants 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 procedure working here http://sqlfiddle.com/#!2/be812/3
Note that this is not the best possible solution, just a (working) sketch of the idea. Also recursion of procedures is disabled by default in mysql (and it's not possible in functions, just procedures), so the invocation should look something like 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;