Is there a way of implementing tree ADT in php and mysql?

Question

Is there a way of storing and working (adding ,removing etc..) with tree data structure in PHP and Mysql?

Can PHP's RecursiveItrator Itrator be of any use here?

So basically I wanna have tree structures, to store some hierarchies like Categories of some products that can go on indefinitely, It would be very nice to be able to store everything in database, fetch them and do simple things like BFS and DSF traversals in them.

possible duplicate of [What is the most efficient/elegant way to parse a flat table into a tree?](http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree) — Bill Karwin, Nov 19 '11 at 00:34
Similar but not duplicate, the table structure in there is very weak, this way of storing, in a book named anti patterns is called the naive way of doing it. That's partially why I'm looking for a better way, I'm not looking only for parsing and storing it, but an easy way of using it, allowing BFS and DSF and other tree iteration techniques — Yasser1984, Nov 19 '11 at 00:46

score 2 · Accepted Answer · edited May 23 '17 at 11:47

A good way to get all the nodes for a given tree when you use Adjacency List is to add a column to every row called root_id or something, so every node knows not only its immediate parent, but also the top node in its tree.

CREATE TABLE Comments (
  comment_id INT PRIMARY KEY,
  root_id INT,
  parent_id INT,
  FOREIGN KEY (root_id) REFERENCES Comments (comment_id),
  FOREIGN KEY (parent_id) REFERENCES Comments (comment_id)
);

So if you have a hierarchy of 10 -> 20 -> 30, you'd store the following:

INSERT INTO Comments SET comment_id = 10, root_id = 10;
INSERT INTO Comments SET comment_id = 20, root_id = 10, parent_id = 10; 
INSERT INTO Comments SET comment_id = 30, root_id = 10, parent_id = 20;

This is similar to how Slashdot stores trees of comments for example.

If you can write a query to fetch all the nodes of a given tree, and each node knows its immediate parent, in the style of the Adjacency List design of storing hierarchical data, you can convert the query result set into a multidimensional array or tree of objects as you fetch it.

See my answer to Convert flat array to the multi-dimentional for code to do this in PHP.

Is there a way of implementing tree ADT in php and mysql?

1 Answers1