Retrieve all nodes in a tree that are children of another one

Question

(Before you down mod it: nope, this is not homework)

I have a web system which has a classical parent-children menu saved in a database, with fields id as the PK, and parent_id to pointing to the owning menu. (Yes, I know this doesn't scale very well, but that's another topic).

So for these records (id-parent_id pairs):

0-7 0-4 4-9 4-14 4-16 9-6

I have this tree:

0
├ 7
└ 4
  ├ 9
  | └ 6     
  ├ 14
  └ 16

I'm needing to hide a top node, so I have to make a list of all the childrens of that certain node, i.e. for 4, they will be (9, 6, 14, 16). Order doesn't matters.

I'm confused... does this fits into the classical tree problems? or is it a graph one?

How can I compose this structure and solve this problem using php?

Answer 1

This is the perfect chance to use recursion!

Pseudo-code:

nodeList = {}
enumerateNodes(rootNode, nodeList);

function enumerateNodes(node, nodeList) {
   nodeList += node;
   foreach ( childnode in node.children ) {
       enumerateNodes(childnode, nodeList);
   }
}

Edit: Didn't notice that your tree is in the adjacent list format. I would probably just build that into an actual tree datastructure before I started working with it. Just loop through all pairs (creating nodes the first time you see them) and linking them. I think it should be easy...

Answer 2

Adjacent list models are very difficult to deal with. The company I am with now uses them for hierarchies and it causes great headaches. I have successfully used Celko's nested set models for prior employers and they work great for creating, maintaining and using hierarchies (trees).

I found this link which describes them: http://www.intelligententerprise.com/001020/celko.jhtml

But I would also recommend the book "SQL for Smarties: Advanced SQL Programming" written by Joe Celko and covers nested sets.

"SQL for Smarties: Advanced SQL Programming (At Amazon): http://tinyurl.com/5beya8

Joe Celko's Trees and Hierarchies in SQL for Smarties(at Amazon): http://tinyurl.com/6nkphm

Answer 3

This is a graph problem. Check out BFS(breadth first search) and DFS(depth first search).. You can google out those terms and find hundreds of implementations on the web.

Answer 4

This is trivial with a nested set implementation. See here for more details:

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

Otherwise, write something like this:

def get_subtree(node)
  if children.size > 0
    return children.collect { |n| get_subtree(n) }
  else
    return node
  end
end